[leetcode] - 14. Longest Common Prefix

14. 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.

풀이

어떤 prefix에 대해서 strs 안에 있는 모든 string들이 prefix로 시작하는지 검증하는 조건식을 세웠다.
근데 뭔가 조잡한 것 같다.

class Solution(object):
    def longestCommonPrefix(self, strs):

        if len(strs) == 1:
            return strs[0]
        ans = ""

        for i in range(len(strs[0])):
            prefix = strs[0][: i + 1]

            if all(string.startswith(prefix) for string in strs):
                ans = prefix
            else:
                break

        return ans

다른 풀이

가장 푼 풀이를 보니 로직은 비슷했다.

array 내부의 첫번째 단어를 가지고 prefix를 만드는데,, 달랐던 점은 그냥 find() 를 쓴 정도?
그리고 나는 이중 for-문인데 이 풀이는 while 문을 사용해서 $O(n\times m)$ (n이 array 크기, m이 가장 긴 string의 길이)의 복잡도로 풀었다.

class Solution:
    def longestCommonPrefix(self, strs):
        if not strs:
            return ""
        prefix = strs[0]
        for string in strs[1:]:
            while string.find(prefix) != 0:
                prefix = prefix[:-1]
                if not prefix:
                    return ""
        return prefix