14. 最长公共前缀
https://leetcode-cn.com/problems/longest-common-prefix/submissions/
解法一:水平搜索
这题与最长公共子串,最长公共子序列的区别在于另两者都是两个串之间的比对,而本题是多个串匹配,限制更多,相互影响,只要有两个串之间不存在公共,那所有串都不存在。
先找strs[0]和strs[1]的共同前缀(注意前缀必须是从头开始的连续子串),以strs[0]为基准前缀,在strs[1]中找,若不存在,前缀尾部截去一个字符,成为新的前缀,直到prefix为空串。
以此类推,在所有串中找一遍。
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
n = len(strs)
if n == 0: return ""
prefix = strs[0] #前缀
for i in range(1, n):
while strs[i].find(prefix) != 0: #若找不到前缀,前缀去尾
prefix = prefix[:len(prefix)-1]
return prefix
解法二:垂直搜索
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
n = len(strs)
if n == 0: return ""
#以0号串为基准
for i in range(len(strs[0])): #对基准的每一位
for j in range(1, n): #比对所有串
#若找到一位与基准串不符,返回(前一个条件为了防越界)
if len(strs[j]) == i or strs[j][i] != strs[0][i]:
return strs[0][:i]
return strs[0] #都符合,则基准就是所求
与上面水平搜索的区别在于,水平是每个串之间比对一遍,垂直是以strs[0]为基准,对其每个字符,在所有串之间比对。好处在于如果有一个最短串位于strs[n-1],长度为p,水平搜索就要遍历所有的串,复杂度为len(strs[0] + strs[1] + ... + strs[n-1])
。而垂直搜索最多只遍历所有的串的前p位,复杂度为p * n = len(strs[n-1]) * n
,也就是说不用遍历所有的情况。
最后更新于