189 8069 5689
大家好！我是Johngo！
成都创新互联公司服务项目包括阜宁网站建设、阜宁网站制作、阜宁网页制作以及阜宁网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，阜宁网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到阜宁省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！
今天不准备一个专题的模块进行分享。
最近在专题制作过程中遇到了最长前缀公共子串的问题，也是读者最近校招面试到的一个题目。为什么拿出这个来说呢？
可怕的是，他居然给了 5 种解题方法。
更可怕的是，因此他直接少了一轮面试，天哪！！
今天顺便分享出来，作为「字符串」的第 5 个部分。
言归正传，这一期来说说字符串的第五块内容 「字符串 - 最长公共前缀」问题
github：https://github.com/xiaozhutec/share_leetcode
文档地址：https://github.com/xiaozhutec/share_leetcode/tree/master/docs
整体架构：
小概念：子串的必须要连续，和子序列不同。
比如说一个字符串 "flower"
子串："flow", "ower", "low" 等等都是它的子串，子串必须要连续；
子序列："flwer", "fler", "wer" 等等都是它的子序列，可以不连续；
但需要注意的是它们的顺序需要和原字符串保持一致。
另外，前缀，一定是从字符串的开头进行计算的。
今天大概说的就是个这...
对，被框住的合集中，就是公共前缀（LCP）!
而且这期只举一个 LeetCode 中比较简单的案例来说明。
思路上比较简单！
但是！就是因为这个思路比较简单，本期就用 5 种方式进行分析。
分别是 Python 提供的 zip 方式解决、横向扫描、纵向扫描、分治、二分法。
整体关于字符串「最长公共前缀」方面的问题。
利用 LeetCode 的 第 14 题，最长公共前缀【简单】来举例！
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
输入：strs = ["flower","flow","flight"] 输出："fl"
熟悉的我的同学都知道，咱们刷题一直用的是 Python 进行刷题，然后也会用到不少 Python 提供的库函数进行问题的解决。
不熟悉 zip 作用的同学不要着急，此处不说原理，10 秒钟用一个例子说明它存在的实际意义。
zip() 函数简单说来，就是将可迭代对象中，各个对应元素打包成一个一个的元祖。
看例子：
>>> str1 = [1,2,3]
>>> str2 = [4,5,6]
>>> str3 = [7,8,9]
>>> zip(str1, str2, str3)
[(1, 4, 7), (2, 5, 8), (3, 6, 9)]
又或者这个例子：
>>> strs = ["flower", "flow", "flight"]
>>> zip(*strs)
[('f', 'f', 'f'), ('l', 'l', 'l'), ('o', 'o', 'i'), ('w', 'w', 'g')]
*str 有解包的作用，即把字符串解为一个一个的字符。
zip() 函数的大概作用明白了吧~
如果仔细看第二个例子的话，其实已经可以看出解决方式了。
将上述各个元祖进行 set 操作去重！
[('f'), ('l'), ('o', 'i'), ('w', 'g')]
继续对各个进行长度计算操作，如果长度为 1 的，那么，前缀必然相同。
即可求出公共前缀了！
图中：最后长度为 1 的字符串，就是咱们要得出来的最长公共前缀了。
简单看下代码：
def longestCommonPrefix1(self, strs):
lcp = ""
for tmp in zip(*strs):
if len(set(tmp)) == 1:
lcp += tmp[0]
else:
break
return lcp
循环比较个字符串的各个位置。
在第一次循环中比较每个字符串的第 0 位，在第二次循环中比较每个字符串的第 1 位，...， 以此类推，直到匹配到不是相同字符。
以下图做一个详细的分析：
tag 表示在比较过程中，是否相同，相同为True，不同为False；
lcp 表示最长公共前缀的长度；
第一次循环：字符都相同，则，tag=True，lcp+1=1
第二次循环：字符都相同，则，tag=True，lcp+1=2
第三次循环：字符在第三个字符比较中出现了不同，则，tag=False，退出循环，得到最终答案。
lcp的值停留在了上一次循环中。。
这就是纵向比较的全部流程，只要遇到不匹配的就退出循环。
下面看下代码实现：
def longestCommonPrefix2(self, strs):
s = strs[0]
size = len(s)
lcp = 0
tag = False
for index in range(size):
# 循环比较每一个位置的字符是否相同
for item in range(len(strs)):
# 需要判断位置 index 在 strs 中字符串是否越界
if index < len(strs[item]) and s[index] == strs[item][index]:
tag = True
else:
# 当匹配不到的时候，退出该次循环
tag = False
break
if tag is True:
lcp += 1
else:
break
return s[:lcp]
下面再看一种方法，是横向比较，即躺着比较，也称为“咸鱼比较法”。
方法一 和 方法二的思路差不多，都是从每一个字符串的每一位进行比较。
横向比较方法，是利用每两个字符串相互比较，保留公共前缀，将保留下来的公共前缀和后面的字符串再进行比较。
还是用这个例子进行说明：strs = ["flower","flow","flight"]
将 0 位置的字符串作为哨兵，与 1 位置的字符串进行比较，得到最长公共前缀。
再用得到的最长公共前缀再与 2 位置的字符串进行比较。得到最后的结果。
以上述例子，看下图：
第一次比较：字符串"flower" 和 "flow" 进行比较，最长公共前缀是 4
第二次比较：将上一步中得到的字符串 “flow” 与下一个字符串再做比较，得到“fl”。
至此，问题解决！
看代码实现：
def longestCommonPrefix3(self, strs):
s = strs[0]
for index in range(1, len(strs)):
w_index, size = 0, min(len(s), len(strs[index]))
for w_index in range(size):
if s[w_index] != strs[index][w_index]:
break
w_index += 1
s = s[0: w_index]
return s
再下面的两种解法是运用了分治和二分的思想。
有很多人可能很容易想到分治的思路，但是立马想不到二分的思路进行解决。
分治思想要比前两种明显感觉要高级一点。。
前两种想法设法的去比较，而当引入分治的时候，就要进行用高级的方式进行比较了。
如下如，分治体现的就是分而治之，部分决策。
将一个大问题，拆分为两个子问题，对子问题继续向下求解。
这个题目就非常清楚的阐明了分治思想的核心。
下面看下这块的代码：
def longestCommonPrefix4(self, strs):
def lcp(left, right):
if left == right:
return strs[left]
mid = (left + right)//2
# 得到左右两个字符串
left_str, right_str = lcp(left, mid), lcp(mid+1, right)
index, min_len = 0, min(len(left_str), len(right_str))
while index < min_len:
if left_str[index] != right_str[index]:
return left_str[:index]
index += 1
return left_str[:index]
return lcp(0, len(strs)-1)
这块是一个典型的二分法的运用。
所以，要理解其中递归的思维逻辑，这个题目就很好的解决了。
再有一个方法呢，就是利用二分的思路进行解决。
还是用 ["flower", "flow", "flownlp", "flowcv"]来举例子。
利用二分查找，以第一个字符串为基准，不断跟后面字符串进行比较。
初始化左右指针以及mid，left=0，right=len(s)-1, mid=(left+right)/2。
"flower" -> left=0,right=5,mid=(left+right)//2=2 => 左:["flo"], 右:["wer"]
如果左:["flo"]在后面每个单词[left:mid]中，说明左侧子串都能够匹配，需要右面子串进行匹配，则 left=mid+1, mid=(left+right)//2
否则，right=mid, mid=(left+right)//2
所以以上述列表中字符串为例：
right=2，mid=1，左:["fl"]，右:["o"]
如果左:["fl"]在后面每个单词[left:mid]中，则 left=mid+1,mid=(left+right)//2
否则，right=mid, mid=(left+right)//2
如果看不清楚，可以看下面图解！
第一次比较：
left=0，right=5，mid=2，发现字符串左半部分"flo"与剩余的每一个字符串都匹配。
所以下面需要进行有半部分的匹配即可，即 left=mid+1！
第二次比较：
left=3，right=5，mid=4，发现子串左半部分"we"与剩余的每一个字符串都不匹配。
因此，需要缩小左半部分的范围，右指针 right=mid。
第三次比较：
left=3，right=4，mid=3，发现子串左半部分"w"与剩余的每一个字符串都匹配。
此时，已经得到了最后的结果。退出循环！
这样看下来，思路也是很清晰，下面用Python来实现一下：
def longestCommonPrefix5(self, strs):
s = strs[0]
lcp = ""
left, right = 0, len(strs[0])-1
mid = (left+right)//2
# 只有一个字符串的情况下
if len(strs) == 1:
return s
while left <= right:
tag = True
# 轮询判断子串与后面每个字符串对应位置的子串是否相同
for i in range(1, len(strs)):
if s[left:mid+1] not in strs[i][left:mid+1]:
tag = False
break
# 左边子串存在后面每个字符串中
if tag is True:
# 将匹配到的子串加入到结果集中
lcp += s[left:mid+1]
left = mid+1
mid = (left+right)//2
# 左边子串不存在后面每个字符串中
else:
if right == mid: # 当 right == mid，说明right指针已经无法靠左移动了，退出循环
break
else:
right = mid
mid = (left+right)//2
return lcp
以上就是就关于字符串「最长公共前缀」的全部分享了。
另外，方便的话也在我的github???? 加颗星，它是我持续输出最大最大的动力，感谢大家！
github：https://github.com/xiaozhutec/share_leetcode
如果感觉内容对你有些许的帮助！
点赞、在看！
评论、转发！
下期想看哪方面的，评论区告诉我！
好了~ 咱们下期见！bye~~