LeetCode: Longest Common Prefix

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 if it is non-empty.

 

생각보다 어려운 문제이다. 

 

모든 단어의 공통된 문자열을 반환해야하는 문제인데, 막상 풀려고 하면 논리를 세우기 힘들다.

 

풀이과정은 다음과 같다.

 

1. 첫 단어를 prefix로 정한다.

 

2. 두 번째 단어부터 비교하여 공통된 문자열로 시작하는지 확인한다. 

 

3. 아니라면 prefix를 한칸 줄인다. 

 

2, 3을 반복하면 문제가 풀린다.

 

 

---

구현코드

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """

        if not strs:
            return ""
    
        prefix = strs[0]  # 첫 단어 기준으로 시작

        for word in strs[1:]:
            while not word.startswith(prefix):
                prefix = prefix[:-1]  # 접두사를 줄여가며 비교
                if prefix == "":
                    return ""
        
        return prefix