目录
题目
-
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1：
输入：strs = ["flower","flow","flight"]
输出："fl"
示例 2：
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
法一、翻译
- 只考虑了含三个字符串的情况
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
i=0
j=0
k=0
re=""
while i < len(strs[0]) and j < len(strs[1]) and k < len(strs[2]):
if strs[0][i] == strs[1][j] == strs[2][k]:
re += strs[0][i]
i+=1
j+=1
k+=1
else:
break
return re
- 正解
- 最长公共前缀最多就是最短的字符串，必定不会超过第一个字符串的长度，所以以第一个字符串为基准进行
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not str:
return ""
for i in range(len(strs[0])):#遍历第一个字符串 strs[0] 中的每个字符。
char = strs[0][i]#存储当前遍历的字符
for j in range(1,len(strs)):#遍历从第二个字符串到最后一个字符串
if i == len(strs[j]) or strs[j][i] != char:#逐个比较每个字符串的当前字符与基准字符是否相同。i不变j变表示不同字符串的同一个位置
return strs[0][:i]
return strs[0]
法二、内置函数zip+set
- 使用zip函数取出每个单词相同位置的字母，转化成集合如果字母相同集合长度为1，如果不同就可以直接返回结果
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
ans = ''
for i in list(zip(*strs)):
if len(set(i)) == 1:
ans += i[0]
else:
break
return ans
# 例子
strs = ["flower","flow","flight"]
list(zip(*strs)) = [('f', 'f', 'f'), ('l', 'l', 'l'), ('o', 'o', 'i'), ('w', 'w', 'g')]
set(('f', 'f', 'f')) = 'f'
set(('o', 'o', 'i')) = {'i','o'}
法三、排序
- 先找出数组中字典序最小和最大的字符串，最长公共前缀即为这两个字符串的公共前缀
# 例子
strs = ["flower","flo","flht"]
#字典序排序后
strs = ["flht","flo","flower"]
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs: return ""
str0 = min(strs)
str1 = max(strs)
for i in range(len(str0)):
if str0[i] != str1[i]:
return str0[:i]
return str0