题目
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1：
输入：strs = ["flower","flow","flight"] 输出："fl"
示例 2：
输入：strs = ["dog","racecar","car"] 输出："" 解释：输入不存在公共前缀。
解题:
方法一：利用python特性
class Solution: def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ res = "" for tmp in zip(*strs): if len(set(tmp)) == 1: res += tmp[0] else: break return res
利用zip(*strs)将每个字符串的第一个都放到了一起。
[‘abc’,‘ab’,‘ab’]那最后答案出来就是ab，而不是abc,因为zip的时候会把多出来的c给去掉
后面别忘了break，不然[“car”,“cer”]会输出"cr"那么就不正确了。
方法二：先排序再比较
class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: if not strs: return "" strs.sort() a = strs[0] b = strs[-1] l = min([len(a),len(b)]) for i in range(l): if a[i]!=b[i]: return a[:i] return a
因为sort()之后，列表内，是按"a"到“z”的顺序排的("a"和"aa"则是"a"在前)，如果第一个字符是一样的，那么就看第二个…
于是只要看第一个和最后一个就行，如果这两个相同，那么中间的一定相同，如果不同，那么直接break
方法三：纵向扫描
class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: if not strs: return "" length, count = len(strs[0]), len(strs) for i in range(length): c = strs[0][i] if any(i == len(strs[j]) or strs[j][i] != c for j in range(1, count)): return strs[0][:i] return strs[0]
每次取开头那个字符穿的第i个数，与后面的比。
其中any(i == len(strs[j]) 是因为可能存在len(strs[j])比i小的情况，而i是在不断增加的，因此取个临界点即可就是想等的时候，按理上说是i>=len(strs[j])。
这个any 是 因为后面有个循环，会出现很多个i == len(strs[1])，i == len(strs[2])等,any是只要有个这样的情况，就说明已经找了最长公共前缀。
方法四：分治
class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: def lcp(start, end):# 其中start 和 end 都是索引，表示的是第几个字符串 if start == end:#如果比较的是同一个字符串，那么直接返回 return strs[start] mid = (start + end) // 2 lcpLeft, lcpRight = lcp(start, mid), lcp(mid + 1, end)#lcpLeft, lcpRight 是两个字符串 minLength = min(len(lcpLeft), len(lcpRight)) for i in range(minLength): if lcpLeft[i] != lcpRight[i]: return lcpLeft[:i] return lcpLeft[:minLength] return "" if not strs else lcp(0, len(strs) - 1)
对于此题来说比较推荐前三种方法，第一种是python特性的方法，第二、三种是比较通用的做法。
第四种分治的方法，主要是了解这种思想。
