[분할정복] LeetCode 14 - Longest Common Prefix

class Solution:

    def merge(self, left, right):
        result = ""
        min_len = min(len(left), len(right))

        for i in range(min_len):
            if left[i] == right[i]:
                result += left[i]
            else:
                return result
        return result

    def divideConquer(self, arr, low, high):
        if low >= high:
            return arr[low]

        m = (low + high) // 2
        leftStr = self.divideConquer(arr, low, m)
        rightStr = self.divideConquer(arr, m + 1, high)

        return self.merge(leftStr, rightStr)

    def longestCommonPrefix(self, strs: List[str]) -> str:
        return self.divideConquer(strs, 0, len(strs) - 1)


if __name__ == '__main__':
    solution = Solution()
    a = ["flower","flow","flight"]
    result = solution.longestCommonPrefix(a)
    print(result)

 

왼쪽부터 문자열 한개만 남을 때까지 쪼갠다.
오른쪽도 쪼갠다.
왼쪽 오른쪽의 공통 prefix 문자열을 구한다. (머지)

flower, flow, flight

왼쪽
- flower,flow
  - flower
  - flow
  - 머지 ! (flower/flow => flow)

오른쪽
- flight

머지!
- flow/flight => fl