Python最长公共子串

方法一

最简单最容易想到的方法，去数组第一个元素为最长公共前缀，如果是，就return，如果不是就减去最后一个单词。只到找到位置。

class Solution:def longestCommonPrefix(self, strs):""":type strs: List[str]:rtype: str"""if len(strs) ==0:return ''prefix = strs[0]for i in range(1,len(strs)):while prefix != strs[i][0:len(prefix)]:prefix = prefix[0:len(prefix)-1]if prefix == '':return ''return prefix

改进版：

class Solution:def longestCommonPrefix(self, strs):""":type strs: List[str]:rtype: str"""if len(strs) == 0:return ""prefix = strs[0]for s in strs:while s.find(prefix) != 0:prefix = prefix[0:len(prefix) - 1]if prefix == "":return prefixreturn prefix

方法二

从第一单词的第一个字母往后加，算法速度和前面差不多。

class Solution:def longestCommonPrefix(self, strs):""":type strs: List[str]:rtype: str"""if len(strs)== 0:return ''prefix =''for i in range(len(strs[0])):prefix += strs[0][i]for x in strs:if x.find(prefix)!=0:return prefix[0:len(prefix)-1]return prefix

方法三

分治法，于排序算法中归并排序的思想类似。

class Solution:def longestCommonPrefix(self, strs):""":type strs: List[str]:rtype: str"""if len(strs) == 0:return ''return self.longest_prefix(strs, 0, len(strs)-1)def longest_prefix(self,strs, I, r):if I == r:return strs[I]else:mid = (I + r) // 2lcpL = self.longest_prefix(strs, I, mid)lcpR = self.longest_prefix(strs, mid + 1, r)return self.commonprefix(lcpL, lcpR)def commonprefix(self,lcpL, lcpR):Min = min(len(lcpL), len(lcpR))for i in range(Min):if lcpL[i] != lcpR[i]:return lcpL[0:i]return lcpL[0:Min]

第四种

二分法：



由此可以看出，二分法还是快的呀！！！

class Solution:def longestCommonPrefix(self, strs):""":type strs: List[str]:rtype: str"""if len(strs) == 0:return ''Min = 2**32for i in strs:Min = min(Min,len(i))low, high = 1, Minwhile low <= high:mid = (low + high) //2if self.iscommonPrefix(strs,mid):low = mid + 1else:high = mid - 1return strs[0][0:(low+high)//2]def iscommonPrefix(self,strs,length):str1 = strs[0][0:length]for i in range(1,len(strs)):if strs[i].find(str1)!=0:return Falsereturn True