python最長公共前綴

題目：

編寫一個函數來查找字符串數組中的最長公共前綴。

如果不存在公共前綴，返回空字符串 ""。

 法一：橫向掃描

LCP(S1 …Sn)=LCP(LCP(LCP(S1,S2),S3),…Sn)

基於該結論，可以得到一種查找字符串數組中的最長公共前綴的簡單方法。依次遍歷字符串數組中的每個字符串，對於每個遍歷到的字符串，更新最長公共前綴，當遍歷完所有的字符串以後，即可得到字符串數組中的最長公共前綴。

class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ""
prefix, count = strs[0], len(strs)
for i in range(1, count):
prefix = self.lcp(prefix, strs[i])
if not prefix:
break
return prefix
def lcp(self, str1, str2):
length, index = min(len(str1), len(str2)), 0
while index < length and str1[index] == str2[index]:
index += 1
return str1[:index]

 法二：縱向掃描

方法一是橫向掃描，依次遍歷每個字符串，更新最長公共前綴。另一種方法是縱向掃描。縱向掃描時，從前往後遍歷所有字符串的每一列，比較相同列上的字符是否相同，如果相同則繼續對下一列進行比較，如果不相同則當前列不再屬於公共前綴，當前列之前的部分為最長公共前綴。

class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ""
result = ""
strs.sort(key=lambda i:len(i))
length, count = len(strs[0]), len(strs)
i = 0
for i in range(length):
c = strs[0][i]
# if any(i == len(strs[j]) or strs[j][i] != c for j in range(1, count)):
for j in range(1, count):
# if i == len(strs[j]) or (strs[j][i]!= c):
if (strs[j][i] != c):
return strs[0][:i]
if i == len(strs[0])-1:
return strs[0][:i+1]#strs=["a","ab"]上段for全部循環完沒有return的時候
return strs[0]#每列元素都相等，例如strs=["",""]
#優化版
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ""
length, count = len(strs[0]), len(strs)
for i in range(length):
c = strs[0][i]
if any(i == len(strs[j]) or strs[j][i] != c for j in range(1, count)):#strs=["ab","a"]時，i==len(strs[j]==1
return strs[0][:i]
return strs[0]#每列元素都相等，例如strs=["",""]
s = ["", ""]
S = Solution()
result = S.longestCommonPrefix(s)
print(result)