14. Longest Common Prefix (Array, String, Trie)

링크 - https://leetcode.com/problems/longest-common-prefix/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Easy

Intuition

1) 첫 글자로 비교

우리는 strs가 2개 이상일 경우, 첫번째 글자를 비교대상으로 삼고 비교를 시작할 수 있다.

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if len(strs) == 1:
            return strs[0]

        ans = ""
        check = strs[0]
        idx = 0
        while True:
            if idx == len(check):
                return ans

            for s in strs[1:]:
                if idx == len(s):
                    return ans
                elif s[idx] != check[idx]:
                    return ans

            ans += check[idx]
            idx +=1

        return ans

Time Complexity: O(S) 여기서 S는 모든 string들의 글자 개수들의 합이다.

Space Complexity: O(1)

2) Divide and Conquer

우리는 strs들을 나눠 2개씩 merge하는 방식으로 문제를 풀 수 있다.

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if len(strs) == 1:
            return strs[0]

        def merge(left, right):
            min_length = min(len(left), len(right))
            for i in range(min_length):
                if left[i] != right[i]:
                    return left[:i]
            return left[:min_length]

        def divide_and_conquer(l, r):
            if l == r:
                return strs[l]

            mid = (l + r) // 2
            left_to_merge = divide_and_conquer(l, mid)
            right_to_merge = divide_and_conquer(mid + 1, r)
            return merge(left_to_merge, right_to_merge)

        return divide_and_conquer(0, len(strs) - 1)

Time Complexity: O(S)

Space Complexity: O(M*logN) m은 string의 길이이고, n은 string의 개수이다.

3) Binary Search

divide and conquer방식과 비슷하게 binary search를 통해 prefix index를 찾아나가는 방법이다.

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if len(strs) == 1:
            return strs[0]

        min_length = min(len(s) for s in strs)
        left, right = 1, min_length

        def isCommonPrefix(end_index):
            prefix = strs[0][:end_index]
            for i in range(len(strs)):
                if strs[i][:end_index] != prefix:
                    return False
            return True

        while left <= right:
            mid = (left + right) // 2
            if isCommonPrefix(mid):
                left = mid + 1
            else:
                right = mid - 1

        return strs[0][:right]

 

Time Complexity: O(S * logM)

Space Complexity: O(1)