1.水平扫描法
思路:
若存在最长公共前缀，即数组中每个字符串均包含公共前缀。于是可以先找出一个公共前缀，然后按顺序比较，对找到的公共前缀进行删减处理，知道最后得到最长的公共前缀。
例如：
["ababcc","ababd","abad","ac"]
①ababcc和ababd比较，得到公共前缀为abab
②abab和abad比较，得到公共前缀aba
③aba和ac比较，得到公共前缀a，所以最长的公共前缀是a
代码：
class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: if len(strs) == 0: return "" result = strs[0] for i in range(1,len(strs)): while strs[i].find(result)!=0: result = result[0:len(result)-1] if result == "": return "" return result
2.垂直扫描法
思路：
从头开始，依次遍历每个字符串的字符，如果相同记录，如果不同退出。
例如：
["ababcc","ababd","abad","abd"]
ababcc ababcc
ababd ababd
abad abad
abd abd
代码：
class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: if len(strs) == 0: return "" for i in range(len(strs[0])): for j in range(1,len(strs)): if i == len(strs[j]) or strs[j][i] != strs[0][i]: return strs[0][0:i] return strs[0]
3.分治法
思路:
采用分治法，对原字符串进行拆分，两两对比找出公共前缀，同样再将对比结果两两对比，知道找到最终结果。
例如：
["ababcc","ababd","abad","abd"]
代码：
class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: if len(strs) == 0: return "" def halfCommonPrefix(strs:List[str],left:int,right:int) ->str: if left == right: return strs[left] else: mid = (left+right)//2 leftStr = halfCommonPrefix(strs,left,mid) rightStr = halfCommonPrefix(strs,mid+1,right) minlen = min(len(leftStr),len(rightStr)) for i in range(minlen): if leftStr[i] != rightStr[i]: return leftStr[0:i] return leftStr[0:minlen] return halfCommonPrefix(strs,0,len(strs)-1)
原文：https://www.cnblogs.com/nilhxzcode/p/12779155.html