Write a function to find the longest common prefix in the string array .
If no common prefix exists , Returns an empty string "".
LCP(S1 …Sn)=LCP(LCP(LCP(S1,S2),S3),…Sn)
Based on this conclusion , You can get a simple way to find the longest common prefix in the string array . Traverse each string in the string array in turn , For each traversed string , Update longest common prefix , After traversing all the strings , You can get the longest common prefix in the string array .
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]The first method is horizontal scanning , Traverse each string in turn , Update longest common prefix . Another method is longitudinal scanning . During longitudinal scanning , Go through each column of all strings from front to back , Compare whether the characters on the same column are the same , If the same, continue to compare the next column , If not, the current column no longer belongs to the public prefix , When the part before the front row is the longest public prefix .
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"] Upper part for Have you finished the cycle return When
return strs[0]# Each column element is equal , for example strs=["",""]
# Optimized version
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"] when ,i==len(strs[j]==1
return strs[0][:i]
return strs[0]# Each column element is equal , for example strs=["",""]
s = ["", ""]
S = Solution()
result = S.longestCommonPrefix(s)
print(result)
Python implements the artificial neural network regression model (mlpressor algorithm) and optimizes the project practice based on gridsearchcv
explain ： This is a practical
