[코딩테스트]리트코드 14 - Longest Common Prefix (Easy) in Python

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"

 

Constraints:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200

 

풀이

1) 완전탐색 - 가로로

문자열 하나 하나, 문자열의 문자 하나 하나를 살펴보되,

그 방향을 가로로 하는 것이다.

(출처 - leetcode.com)

문자열 1과 2를 먼저 비교해서 이 둘의 가장 긴 접미사 (LCP{1, 2})를 찾고,

문자열 3과 LCP{1,2}를 비교해서 이 둘의 가장 긴 접미사 (LCP{1, 3})를 찾고,

이런 식으로 나아가 LCP{1, n}을 찾는 방법이다.

 

시간 복잡도 - 모든 문자열의 모든 문자를 살펴보므로, 시간 복잡도는 O(s), s는 모든 문자의 합이다.

문제에서 주어진 constraints로 볼 때 O(s) = O(200 * 200) = O(40000)으로 안정적으로 탐색할 수 있음을 볼 수 있다.

 

공간 복잡도 - 각 비교 단계에서 LCP를 저장할 공간만이 추가적으로 필요하므로, O(1)이다

 

2) 완전 탐색 - 세로로

1번 방법과 비슷하되, 탐색 방향을 세로로 하는 것이다.

각 비교 단계에서, 모든 문자열의 index i에 해당하는 문자를 검사한다.

 

나는 처음에 이 방식으로 풀게 되었다.

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        answer = ''
        strs.sort()
        for i in range(len(strs[0])):
            curr = strs[0][i]
            if self.includesCharacter(strs,curr,i):
                answer += curr
            else:
                break
        return answer
            
    def includesCharacter(self, strs, curr, i):
        for x in strs[1:]:
            if x[i] == curr:
                continue
            else:
            	return False
        return True

시간 복잡도 - 역시나 모든 문자열의 모든 문자를 검사하므로, O(s)가 된다.

공간 복잡도 - 같은 이유로 O(1)

 

똑같은 알고리즘을

훨씬 더 깔끔하게 푸신 분이 있어 여기다 복기한다.

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs: #빈 배열이면
        	return ''
        minStr = min(strs, key = len)
        for i, x in enumerate(minStr):
        	for other in strs:
            	if other[i] !=x:
                	return minStr[:i]
        return minStr

 

 

리트코드에서는 분할정복알고리즘과 이분탐색 방법도 소개하지만, 시간 복잡도 면에서 더 낫지 않고 반응도 별로여서.. 소개하지 않는다.

 

다만 Trie구조로 문자열을 배열하는 연습은 필수적이기에, 다른 문제 풀이에서 다루도록 해야겠다.

https://leetcode.com/problems/implement-trie-prefix-tree/

Implement Trie (Prefix Tree) - LeetCode

(^요문제)