题目

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

输出：strs = ["flower","flow","flight"]
输入："fl"

纵向扫描

最间接的思路：
选取第一个字符串假如为前缀。
用这个前缀的每一个字符，去和所有其余字符串比拟，如果其余字符串在该地位也是这个字符，那这个字符就属于前缀；反之，前缀就到此结束。

不须要思考选取数组中的第一个字符串是否长度是最小或最长的。因为最差状况就是这个字符串是长度最短的，并且所有字符刚好都是前缀。

工夫复杂度：最坏状况，数组有 n 个字符串，字符串全都一样且长度为 m，O(mn)
空间复杂度：O(1)

def longestCommonPrefix(strs):
    firstStr = strs[0]
    for i in range(len(firstStr)):
        for str in strs[1:]:
            if str[i] != firstStr[i]:
                return firstStr[0:i] if i > 0 else ''

横向扫描

假如数组中第一个字符串是前缀。
拿假如前缀，和第二个字符串比拟，共有局部是新的前缀。
再拿新的前缀，和第三个字符串比拟，共有局部是新的前缀。
始终如此，比到数组最初一个字符串。

工夫复杂度：最坏状况和之前一样，O(mn)
空间复杂度：O(1)

def longestCommonPrefix(strs):
    prefix = strs[0]
    for str in strs[1:]:
        # 选较短长度作为遍历范畴
        for i in range(min(len(prefix), len(str))):
            if prefix[i] != str[i]:
                prefix = prefix[:i]
                break
    return prefix

分治法

分治法是一种思维，就是分而治之。

递归是一种编程技巧，分治思维在代码中适宜用递归来实现。

在本题中，将原数组分成两半，别离找出这两局部的公共前缀，再找出这两个前缀的公共前缀，最终就是这个数组的公共前缀。这就是分治思维

工夫复杂度 O(mn)
空间复杂度 O(mlogn)，m 是字符串均匀长度，n 是字符串数量

def longestCommonPrefix(strs):
    def split(start, end):
        # 分到不可再分，返回字符串
        if start == end:
            return strs[start]
        mid = (start + end) // 2
        # 递归宰割数组
        left, right = split(start, mid), split(mid + 1, end)
        # 以两个字符串中较小的长度作为遍历范畴
        minLen = min(len(left), len(right))
        print(left, right, minLen)
        for i in range(minLen):
            # 当呈现不统一，则该层公共前缀已找到
            if left[i] != right[i]:
                return left[:i]
        # 没有不统一，长度较小的字符串全副遍历完，则长度较小的字符串就是公共前缀
        return left[:minLen]

    return split(0, len(strs) - 1)

二分法

公共前缀的长度肯定不会超过最小长度的字符串。
咱们再最小长度字符串上应用二分法，将其分成两半，用左半边字符去和每个字符串比拟
如果每个字符串都有，那么就挪动左指针
如果有字符串没有，那么就挪动右指针，放大公共范畴

工夫复杂度：O(mnlogm)，其中 m 是字符串数组中的字符串的最小长度，n 是字符串的数量。二分查找的迭代执行次数是 O(logm)，每次迭代最多须要比拟 mn 个字符，因而总工夫复杂度是 O(mnlogm)。

空间复杂度：O(1)O(1)。应用的额定空间复杂度为常数。

def longestCommonPrefix(strs):
    minLen = min(len(str) for str in strs)
    left, right = 0, minLen - 1
    # 循环条件是 <=，left 和 right 会挪动到同一个字符上，有 == 的状况
    while left <= right:
        mid = (left + right) // 2
        # all()函数，全副为 True 返回 True
        allTrue = all(strs[0][:mid + 1] == str[:mid + 1] for str in strs)
        if allTrue:
            left = mid + 1
        else:
            right = mid - 1
    return strs[0][:left]