(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 lower-case English letters.

해당 문제는 간단해 보이지만 여러 가지 솔루션으로 해결할 수 있는 흥미로운 문제다. LeetCode에서 직접 다양한 알고리즘을 통한 해결 방법을 보여주고(java 코드) 시간 및 공간 복잡도 설명도 하고 있다.

아래 대표적으로 1) vertical scanning, 2) binary search, 3) divide and conquer 코드를 설명한다.

# vertical scanning
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        strs.sort(key=lambda x: len(x)) 
        
        # strs가 empty인 경우
        if len(strs) == 0:
            return
        else:
            for i in range(len(strs[0])):
                for j in range(1, len(strs)):
                    if strs[0][i] != strs[j][i]: # 달라지는 순간 그때까지의 원소 리턴
                        return strs[0][:i]
            return strs[0]

strs 원소 개수: n
가장 짧은 원소 글자 수: m
time complexity: $O(n \times logn)$
-> for loop의 시간 복잡도는 $O(m \times n)$ + sort함수 시간 복잡도 $O(logn)$

---

# binary search
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if len(strs) == 0:
            return
        else:
            target = strs[0]
            
            remains = strs[1:]
            if not remains: # strs에 1개 원소밖에 없을 때
                return target
            left = 0
            right = len(target) - 1
            
            mid = ((left + right) // 2)
            while left <= right:
                # 공통 글자들인지 확인
                if self.isCommonPrefix(target[:mid + 1], remains):
                    left = mid + 1
                else:
                    right = mid - 1
                mid = ((left + right) // 2)
        return target[:mid + 1]
                
                
    def isCommonPrefix(self, target, remains):
        for x in remains:
            if not x.startswith(target): # 남은 원소들의 시작하는 글자 확인
                return False
        return True

strs 원소 개수: n
각 원소 글자 수: m
time complexity: $O(n \times m \times logm)$
-> binary search의 시간 복잡도는 $O(logm)$, 최악의 경우 strs 원소 개수 x 각 원소 글자 수만큼 모두 훑어봐야 함

---

# divide and conquer
class Solution:
    def commonPrefix(self, str1, str2):
        result = ''
        i, j = 0, 0
        
        while i <= len(str1) - 1 and j <= len(str2) - 1:
            if str1[i] != str2[j]: # 공통 글자인지 확인
                break
            result += str1[i]
            i, j = i + 1, j + 1
        return result
    
    def longestCommonPrefixHelp(self, strs: List[str], low: int, high: int) -> str:
        if low == high:
            return strs[low]
        
        if high > low:
            mid = low + (high - low) // 2
            
            str1 = self.longestCommonPrefixHelp(strs, low, mid)
            str2 = self.longestCommonPrefixHelp(strs, mid + 1, high)
            
            return self.commonPrefix(str1, str2)
        
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if len(strs) == 0:
            return
        return self.longestCommonPrefixHelp(strs, 0, len(strs) - 1)

strs 원소 개수: n
각 원소 글자 수: m
time complexity: $O(m \times n)$
space complexity: $O(m \times logn)$
-> $logn$번의 재귀 반복 진행, 각각 $m$개의 공간을 통해 결과 저장