分治算法求最長公共字首

編寫一個函數來查找字元串數組中的最長公共字首。

如果不存在公共字首，傳回空字元串 ""。

示例 1：

輸入：strs = ["flower","flow","flight"]

輸出："fl"

示例 2：

輸入：strs = ["dog","racecar","car"]

輸出：""

解釋：輸入不存在公共字首。

提示：

1 <= strs.length <= 200

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

strs[i] 僅由小寫英文字母組成

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        def lcp(start, end):
            if start == end:
                return strs[start]
              
            mid = (start + end) // 2
            Lcp_left, Lcp_right = lcp(start,mid), lcp(mid+1,end)
            min_length = min(len(Lcp_left), len(Lcp_right))
            for i in range(min_length):
                if Lcp_left[i] != Lcp_right[i]:
                    return Lcp_left[:i]
            return Lcp_left[:min_length]


        # if not strs:
        #     return ""
        # else:
        #     return lcp(0,len(strs)-1)

        return "" if not strs else lcp(0, len(strs) - 1)
           

分支算法：分而治之，采用遞歸調用，每次調用都兵分兩路同時進行。

二分法：查找數列中某個元素的位置，從兩邊向中間逼近，直至找到所需值，或兩邊指針相錯開，則查找無值。