通过一个函数来查找数组中所有的字符串最长公共前缀。(第一个是我写的,后面有几个很经典的,看不懂请看力扣官网)
class Solution(object):
def longestCommonPrefix1(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
length = len(strs)
if not length:
return ""
i = 0
prepare_str = strs[0]
inner_length = len(min(strs, key=len))
while i < inner_length:
flag = True # 判断是否发现了不一样的字符串
for j in range(1, length):
if strs[j][i] != prepare_str[i]:
flag = False
break
if not flag or i + 1 > inner_length:
break
i += 1
return prepare_str[:i]
def longestCommonPrefix2(self, strs):
"""这个方法很好,先将和第二个字符串相同的留下,每次会是的subStr长度减少
:type strs: List[str]
:rtype: str
"""
if len(strs) == 0:
return ""
strs = sorted(strs)
subStr = strs[0]
for i in range(1, len(strs)):
while strs[i].find(subStr) != 0:
subStr = subStr[:-1]
if subStr == "":
return subStr
return subStr
def longestCommonPrefix3(self, strs):
"""说实话看不懂
:type strs: List[str]
:rtype: str
"""
def lcp(start, end):
if start == end:
return strs[start]
mid = (start + end) // 2
lcpLeft, lcpRight = lcp(start, mid), lcp(mid + 1, end)
minLength = min(len(lcpLeft), len(lcpRight))
for i in range(minLength):
if lcpLeft[i] != lcpRight[i]:
return lcpLeft[:i]
return lcpLeft[:minLength]
return "" if not strs else lcp(0, len(strs) - 1)
def longestCommonPrefix4(self, strs):
s=""
zip_str = zip(*strs)
for i in zip_str:
if len(set(i)) == 1:
s += i[0]
else:
return s
return s
def longestCommonPrefix5(self, strs) -> 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)):
return strs[0][:i]
return strs[0]
def longestCommonPrefix6(self, strs) -> str:
def lcp(start, end):
if start == end:
return strs[start]
mid = (start + end) // 2
inner_left, inner_right = lcp(start, mid), lcp(mid + 1, end)
min_len = min(len(inner_left), len(inner_right))
for i in range(min_len):
if inner_left[i] != inner_right[i]:
return inner_left[:i]
return inner_left[:min_len]
left, right = 0, len(strs) - 1
return "" if not strs else lcp(left, right)
def longestCommonPrefix(self, strs) -> str:
"""二分法查找还可以这样用,很经典"""
def is_common_prefix(length):
str0, count = strs[0][:length], len(strs)
return all(strs[i][:length] == str0 for i in range(1, count))
if not strs:
return ""
min_length = min(len(s) for s in strs)
low, high = 0, min_length
while low < high:
mid = (high - low + 1) // 2 + low
if is_common_prefix(mid):
low = mid
else:
high = mid - 1
return strs[0][:low]
if __name__ == '__main__':
s = Solution()
strs = ["flower", "flow", "flight"]
# strs = ["dog", "d","dacecar", "d"]
# strs = [""]
print(s.longestCommonPrefix(strs))