[String] 14. Longest Common Prefix / startswith() 함수

https://leetcode.com/problems/longest-common-prefix/description/

 

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

 

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

 

Constraints:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] consists of only lowercase English letters.

---

• startswith()

접두어, 접미어를 파악하기 위해 파이썬에서 제공되는 startwith(), endwith()를 사용할 수 있다.

다음의 함수를 사용할 경우 접두(미)어를 쉽게 찾을 수 있으며 dictionary 타입에서도 사용 가능

 

예시

sentence = "girl's generation"

result = sentence.startswith('girl')
print(result)

# 출력결과: True

 

• endswith()

idol = [
    "girl's generation",
    "black pink",
    "A-pink",
    "aespa"
]

for i in idol:
    # 문자열을 소문자로 변환한 후, 'pink'로 끝나는지 확인
    if i.lower().endswith('pink'):
        print(i)  # 문자열 출력
    else:
        print("")  # 빈 문자열 출력
        
#출력결과
#black pink
#A-pink

---

 

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return "" #빈 리스트 입력 시 빈 문자열 반환
        
        short_str = min(strs, key=len) # 사전순이 아닌 문자열 길이로 최소값 찾기
        for i in range(len(short_str)): # 가장 짧은 문자열 기준으로
            for s in strs: # 기존 strs 리스트 내 요소들과 비교
                if s[i] != short_str[i]: # 더이상 일치하는 문자가 없으면
                    return short_str[:i] # i-1번째까지 문자열 출력
        
        return short_str #모든 문자열이 공통 접두어일 경우

for문으로 문자열을 하나하나 돌면서 비교하거나 "가장 짧은 문자열"로 비교하면 효율적이다.

 

+) 빈 문자열이 입력으로 주어진 경우에도 ""로 처리해야 한다고 한다.

그냥 공통 접두사어가 없으면 ""로 반환하는 것만 생각했었기에 처음엔 떠오르지 않았다.

 

 

 

가장 짧은 문자열을 기준으로 비교하므로, strs 리스트 내의 요소 s도 인덱스를 i까지만 돌면 된다.

앞에서부터 i-1번째까지 출력하면 접두어를 뽑아낼 수 있다.

 

*슬라이스 범위

 

• start: 슬라이스의 시작 인덱스 (포함).
  • 생략하면 0으로 간주
• end: 슬라이스의 종료 인덱스 (미포함).
  • 인덱스 end에 해당하는 문자는 포함되지 않음
• step: 문자열을 몇 칸씩 건너뛸지를 지정합니다. 기본값은 1

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return "" #빈 리스트 입력 시 빈 문자열 반환
        
        short_str = min(strs, key=len) # 사전순이 아닌 문자열 길이로 최소값 찾기
        for i in range(len(short_str)): # 가장 짧은 문자열 기준으로
            for s in strs: # 기존 strs 리스트 내 요소들과 비교
                if s[i] != short_str[i]: # 더이상 일치하는 문자가 없으면
                    return short_str[:i] # i-1번째까지 문자열 출력

 

여기까지만 구현했을 경우, 가장 짧은 문자열이 다른 문자열들과 비교했을 때 전체가 공통 접두어가 될 경우에 대한 결과가 빠져있으므로 short_str 자체를 리턴하는 부분도 넣어야 한다.

 

 

 

👩‍🌾 ["dog","racecar","car"] 처럼 공통접두어가 존재하지 않는 경우에 대한 처리는 어디서?

 

for i in range(len(short_str)): # 가장 짧은 문자열 기준으로
            for s in strs: # 기존 strs 리스트 내 요소들과 비교
                if s[i] != short_str[i]: # 더이상 일치하는 문자가 없으면
                    return short_str[:i] # i-1번째까지 문자열 출력

 

해당 for문 안에서 슬라이싱 문법으로 i-1번째까지 출력이므로, 공통 접두어가 없을 경우 자연스럽게 끝나고 "" 빈 문자열을 반환하게 된다.