[Algorithm][LCP] LeetCode 14 - Longest Common Prefix

알고리즘 분류

 Longest Common Prefix

 

시간 복잡도

 $O(mn)$

 

문제 링크

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

---

 이번 문제의 알고리즘 종류는 LCP(Longest Common Prefix)입니다. LeetCode에서 Easy 난이도의 문제로 등록되어 있지만, 여러가지 문제 풀이 방법들이 존재합니다. 저는 여러가지 방법 중 분할기법(Devide and Conquer)을 사용했습니다.

 

 String 리스트가 주어질 때 리스트 길이가 1이 될 때까지 index를 계속 두 그룹으로 나눠줍니다. 재귀 함수를 사용하여 쉽게 구현할 수 있습니다. 해당 재귀 함수는 String끼리 비교하며 LCP를 구하며 가장 처음의 함수까지 올라옵니다. 아래 그림을 보면 더 쉽게 이해할 수 있습니다.

 

 

 이 때 두 String을 비교하는 과정에서 두 String 중 짧은 길이만큼 반복문을 돌려 부분 LCP를 구할 수 있습니다. 하지만 String 리스트 중 가장 짧은 String 길이만큼만 반복문을 돌리면 좀 더 빠른 실행 속도를 낼 수 있습니다. 왜냐하면 분할로 LCP를 비교하며 정답을 도출하겠지만, 결국 정답의 길이는 가장 짧은 String 길이를 넘을 수 없기 때문입니다.

 

 시간복잡도를 계산하면 2분할로 나눠지므로 아래부터 올라오면서 두 String을 비교하는 횟수는 $n-1$번입니다. 그리고 각 비교 때마다 String 리스트 중 가장 짧은 길이인 $m$의 시간이 걸리기 때문에 최종적인 시간 복잡도는 $O(mn)$입니다. (실제로는 비교하면서 LCP의 길이를 업데이트하기 때문에 m보다 짧아질 수 있습니다.)

 

Python

class Solution:
    inputStrs = []
    minLen = 0
    
    def longestCommonPrefix(self, strs: List[str]) -> str:
        self.inputStrs = strs
        self.minLen = min([len(x) for x in strs])
        
        return self.devideAndConquer(0,len(strs)-1)
        
    def findLongestPrefix(self, str1, str2) -> str:
        for idx in range(0,self.minLen):
            if str1[idx] != str2[idx]:
                self.minLen = idx
                return str1[:idx]
            
        return str1[:self.minLen]
            
    def devideAndConquer(self, si: int, ei: int) -> str:
        if si == ei:
            return self.inputStrs[si]
        
        mid = int((si+ei)/2)
        res1 = self.devideAndConquer(si,mid)
        res2 = self.devideAndConquer(mid+1,ei)
        
        return self.findLongestPrefix(res1, res2)