编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""。
示例 1:
输入:strs = ["flower","flow","flight"]
输出:"fl"
示例 2:
输入:strs = ["dog","racecar","car"]
输出:""
解释:输入不存在公共前缀。
提示:
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/longest-common-prefix
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解1:
执行用时:52 ms, 在所有 Python3 提交中击败了18.04%的用户
内存消耗:16.1 MB, 在所有 Python3 提交中击败了35.03%的用户
通过测试用例:124 / 124
查看代码
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
res = strs[0]
res_len = len(res)
for item in strs:
item_len = len(item)
if item_len == 0:
res = ""
break
min_len = min(res_len, item_len)
temp = ""
for i in range(0, min_len):
if res[i] == item[i]:
temp += res[i]
else:
break
if temp == "":
res = ""
break
res = temp
res_len = len(res)
return res
题解2:
执行用时:48 ms, 在所有 Python3 提交中击败了34.82%的用户
内存消耗:15.9 MB, 在所有 Python3 提交中击败了68.82%的用户
通过测试用例:124 / 124
查看代码
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
res = ""
min_len = 200
for item in strs:
min_len = min(min_len, len(item))
if min_len == 0:
return res
for i in range(0, min_len):
temp = ""
for item in strs:
s = item[i:i + 1]
if temp == "":
temp = s
elif s != temp:
return res
res = res + temp
return res
题解4:
执行用时:52 ms, 在所有 Python3 提交中击败了18.04%的用户
内存消耗:16.2 MB, 在所有 Python3 提交中击败了26.22%的用户
通过测试用例:124 / 124
查看代码
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
res = ""
inversion_list = [""] * 200
for item in strs:
if item == "":
return res
item_list = list(item)
inversion_list = list(map(lambda x, y: x + y, inversion_list, item_list))
for item in inversion_list:
if min(item) == max(item):
res = res + item[0]
else:
break
return res
题解5:
124 / 124 个通过测试用例
状态:通过执行用时: 36 ms
内存消耗: 16.2 MB
查看代码
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
res = ""
min_len = 200
index = 0
while True:
if index == min_len:
break
temp = ""
for item in strs:
if index == 0:
min_len = min(min_len, len(item))
if min_len == 0:
return res
s = item[index: index + 1]
if temp == "":
temp = s
elif s != temp:
return res
res = res + temp
index = index + 1
return res