题目

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

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

输出：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]