大家好！我是Johngo！
成都創(chuàng)新互聯(lián)公司服務(wù)項(xiàng)目包括阜寧網(wǎng)站建設(shè)、阜寧網(wǎng)站制作、阜寧網(wǎng)頁(yè)制作以及阜寧網(wǎng)絡(luò)營(yíng)銷策劃等。多年來(lái)，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢(shì)、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，阜寧網(wǎng)站推廣取得了明顯的社會(huì)效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到阜寧省份的部分城市，未來(lái)相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！
今天不準(zhǔn)備一個(gè)專題的模塊進(jìn)行分享。
最近在專題制作過(guò)程中遇到了最長(zhǎng)前綴公共子串的問(wèn)題，也是讀者最近校招面試到的一個(gè)題目。為什么拿出這個(gè)來(lái)說(shuō)呢？
可怕的是，他居然給了 5 種解題方法。
更可怕的是，因此他直接少了一輪面試，天哪！！
今天順便分享出來(lái)，作為「字符串」的第 5 個(gè)部分。
言歸正傳，這一期來(lái)說(shuō)說(shuō)字符串的第五塊內(nèi)容 「字符串 - 最長(zhǎng)公共前綴」問(wèn)題
github：https://github.com/xiaozhutec/share_leetcode
文檔地址：https://github.com/xiaozhutec/share_leetcode/tree/master/docs
整體架構(gòu)：
小概念：子串的必須要連續(xù)，和子序列不同。
比如說(shuō)一個(gè)字符串 "flower"
子串："flow", "ower", "low" 等等都是它的子串，子串必須要連續(xù)；
子序列："flwer", "fler", "wer" 等等都是它的子序列，可以不連續(xù)；
但需要注意的是它們的順序需要和原字符串保持一致。
另外，前綴，一定是從字符串的開(kāi)頭進(jìn)行計(jì)算的。
今天大概說(shuō)的就是個(gè)這...
對(duì)，被框住的合集中，就是公共前綴（LCP）!
而且這期只舉一個(gè) LeetCode 中比較簡(jiǎn)單的案例來(lái)說(shuō)明。
思路上比較簡(jiǎn)單！
但是！就是因?yàn)檫@個(gè)思路比較簡(jiǎn)單，本期就用 5 種方式進(jìn)行分析。
分別是 Python 提供的 zip 方式解決、橫向掃描、縱向掃描、分治、二分法。
整體關(guān)于字符串「最長(zhǎng)公共前綴」方面的問(wèn)題。
利用 LeetCode 的 第 14 題，最長(zhǎng)公共前綴【簡(jiǎn)單】來(lái)舉例！
編寫一個(gè)函數(shù)來(lái)查找字符串?dāng)?shù)組中的最長(zhǎng)公共前綴。
如果不存在公共前綴，返回空字符串 ""。
輸入：strs = ["flower","flow","flight"] 輸出："fl"
熟悉的我的同學(xué)都知道，咱們刷題一直用的是 Python 進(jìn)行刷題，然后也會(huì)用到不少 Python 提供的庫(kù)函數(shù)進(jìn)行問(wèn)題的解決。
不熟悉 zip 作用的同學(xué)不要著急，此處不說(shuō)原理，10 秒鐘用一個(gè)例子說(shuō)明它存在的實(shí)際意義。
zip() 函數(shù)簡(jiǎn)單說(shuō)來(lái)，就是將可迭代對(duì)象中，各個(gè)對(duì)應(yīng)元素打包成一個(gè)一個(gè)的元祖。
看例子：
重慶分公司
重慶分公司
>>> 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)]
又或者這個(gè)例子：
>>> strs = ["flower", "flow", "flight"]
>>> zip(*strs)
[('f', 'f', 'f'), ('l', 'l', 'l'), ('o', 'o', 'i'), ('w', 'w', 'g')]
*str 有解包的作用，即把字符串解為一個(gè)一個(gè)的字符。
zip() 函數(shù)的大概作用明白了吧~
如果仔細(xì)看第二個(gè)例子的話，其實(shí)已經(jīng)可以看出解決方式了。
將上述各個(gè)元祖進(jìn)行 set 操作去重！
[('f'), ('l'), ('o', 'i'), ('w', 'g')]
繼續(xù)對(duì)各個(gè)進(jìn)行長(zhǎng)度計(jì)算操作，如果長(zhǎng)度為 1 的，那么，前綴必然相同。
即可求出公共前綴了！
圖中：最后長(zhǎng)度為 1 的字符串，就是咱們要得出來(lái)的最長(zhǎng)公共前綴了。
簡(jiǎn)單看下代碼：
def longestCommonPrefix1(self, strs):
lcp = ""
for tmp in zip(*strs):
if len(set(tmp)) == 1:
lcp += tmp[0]
else:
break
return lcp
循環(huán)比較個(gè)字符串的各個(gè)位置。
在第一次循環(huán)中比較每個(gè)字符串的第 0 位，在第二次循環(huán)中比較每個(gè)字符串的第 1 位，...， 以此類推，直到匹配到不是相同字符。
以下圖做一個(gè)詳細(xì)的分析：
tag 表示在比較過(guò)程中，是否相同，相同為True，不同為False；
lcp 表示最長(zhǎng)公共前綴的長(zhǎng)度；
第一次循環(huán)：字符都相同，則，tag=True，lcp+1=1
第二次循環(huán)：字符都相同，則，tag=True，lcp+1=2
第三次循環(huán)：字符在第三個(gè)字符比較中出現(xiàn)了不同，則，tag=False，退出循環(huán)，得到最終答案。
lcp的值停留在了上一次循環(huán)中。。
這就是縱向比較的全部流程，只要遇到不匹配的就退出循環(huán)。
下面看下代碼實(shí)現(xiàn)：
def longestCommonPrefix2(self, strs):
s = strs[0]
size = len(s)
lcp = 0
tag = False
for index in range(size):
# 循環(huán)比較每一個(gè)位置的字符是否相同
for item in range(len(strs)):
# 需要判斷位置 index 在 strs 中字符串是否越界
if index < len(strs[item]) and s[index] == strs[item][index]:
tag = True
else:
# 當(dāng)匹配不到的時(shí)候，退出該次循環(huán)
tag = False
break
if tag is True:
lcp += 1
else:
break
return s[:lcp]
下面再看一種方法，是橫向比較，即躺著比較，也稱為“咸魚(yú)比較法”。
方法一 和 方法二的思路差不多，都是從每一個(gè)字符串的每一位進(jìn)行比較。
橫向比較方法，是利用每?jī)蓚€(gè)字符串相互比較，保留公共前綴，將保留下來(lái)的公共前綴和后面的字符串再進(jìn)行比較。
還是用這個(gè)例子進(jìn)行說(shuō)明：strs = ["flower","flow","flight"]
將 0 位置的字符串作為哨兵，與 1 位置的字符串進(jìn)行比較，得到最長(zhǎng)公共前綴。
再用得到的最長(zhǎng)公共前綴再與 2 位置的字符串進(jìn)行比較。得到最后的結(jié)果。
以上述例子，看下圖：
第一次比較：字符串"flower" 和 "flow" 進(jìn)行比較，最長(zhǎng)公共前綴是 4
第二次比較：將上一步中得到的字符串 “flow” 與下一個(gè)字符串再做比較，得到“fl”。
至此，問(wèn)題解決！
看代碼實(shí)現(xiàn)：
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
再下面的兩種解法是運(yùn)用了分治和二分的思想。
有很多人可能很容易想到分治的思路，但是立馬想不到二分的思路進(jìn)行解決。
分治思想要比前兩種明顯感覺(jué)要高級(jí)一點(diǎn)。。
前兩種想法設(shè)法的去比較，而當(dāng)引入分治的時(shí)候，就要進(jìn)行用高級(jí)的方式進(jìn)行比較了。
如下如，分治體現(xiàn)的就是分而治之，部分決策。
將一個(gè)大問(wèn)題，拆分為兩個(gè)子問(wèn)題，對(duì)子問(wèn)題繼續(xù)向下求解。
這個(gè)題目就非常清楚的闡明了分治思想的核心。
下面看下這塊的代碼：
def longestCommonPrefix4(self, strs):
def lcp(left, right):
if left == right:
return strs[left]
mid = (left + right)//2
# 得到左右兩個(gè)字符串
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)
這塊是一個(gè)典型的二分法的運(yùn)用。
所以，要理解其中遞歸的思維邏輯，這個(gè)題目就很好的解決了。
再有一個(gè)方法呢，就是利用二分的思路進(jìn)行解決。
還是用 ["flower", "flow", "flownlp", "flowcv"]來(lái)舉例子。
利用二分查找，以第一個(gè)字符串為基準(zhǔn)，不斷跟后面字符串進(jìn)行比較。
初始化左右指針以及mid，left=0，right=len(s)-1, mid=(left+right)/2。
"flower" -> left=0,right=5,mid=(left+right)//2=2 => 左:["flo"], 右:["wer"]
如果左:["flo"]在后面每個(gè)單詞[left:mid]中，說(shuō)明左側(cè)子串都能夠匹配，需要右面子串進(jìn)行匹配，則 left=mid+1, mid=(left+right)//2
否則，right=mid, mid=(left+right)//2
所以以上述列表中字符串為例：
right=2，mid=1，左:["fl"]，右:["o"]
如果左:["fl"]在后面每個(gè)單詞[left:mid]中，則 left=mid+1,mid=(left+right)//2
否則，right=mid, mid=(left+right)//2
如果看不清楚，可以看下面圖解！
第一次比較：
left=0，right=5，mid=2，發(fā)現(xiàn)字符串左半部分"flo"與剩余的每一個(gè)字符串都匹配。
所以下面需要進(jìn)行有半部分的匹配即可，即 left=mid+1！
第二次比較：
left=3，right=5，mid=4，發(fā)現(xiàn)子串左半部分"we"與剩余的每一個(gè)字符串都不匹配。
因此，需要縮小左半部分的范圍，右指針 right=mid。
第三次比較：
left=3，right=4，mid=3，發(fā)現(xiàn)子串左半部分"w"與剩余的每一個(gè)字符串都匹配。
此時(shí)，已經(jīng)得到了最后的結(jié)果。退出循環(huán)！
這樣看下來(lái)，思路也是很清晰，下面用Python來(lái)實(shí)現(xiàn)一下：
def longestCommonPrefix5(self, strs):
s = strs[0]
lcp = ""
left, right = 0, len(strs[0])-1
mid = (left+right)//2
# 只有一個(gè)字符串的情況下
if len(strs) == 1:
return s
while left <= right:
tag = True
# 輪詢判斷子串與后面每個(gè)字符串對(duì)應(yīng)位置的子串是否相同
for i in range(1, len(strs)):
if s[left:mid+1] not in strs[i][left:mid+1]:
tag = False
break
# 左邊子串存在后面每個(gè)字符串中
if tag is True:
# 將匹配到的子串加入到結(jié)果集中
lcp += s[left:mid+1]
left = mid+1
mid = (left+right)//2
# 左邊子串不存在后面每個(gè)字符串中
else:
if right == mid: # 當(dāng) right == mid，說(shuō)明right指針已經(jīng)無(wú)法靠左移動(dòng)了，退出循環(huán)
break
else:
right = mid
mid = (left+right)//2
return lcp
以上就是就關(guān)于字符串「最長(zhǎng)公共前綴」的全部分享了。
另外，方便的話也在我的github???? 加顆星，它是我持續(xù)輸出最大最大的動(dòng)力，感謝大家！
github：https://github.com/xiaozhutec/share_leetcode
如果感覺(jué)內(nèi)容對(duì)你有些許的幫助！
點(diǎn)贊、在看！
評(píng)論、轉(zhuǎn)發(fā)！
下期想看哪方面的，評(píng)論區(qū)告訴我！
好了~ 咱們下期見(jiàn)！bye~~
