LeetCode-14 最长公共前缀

题目:最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 ""

示例 1:

1
2
输入: ["flower","flow","flight"]
输出: "fl"

示例 2:

1
2
3
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明:

所有输入只包含小写字母 a-z

思路

这个题免不了得一个个的对比,由于是公共字符串,那么最长公共前缀的可能性就是list中长度最短的那个字符串的长度,然后依次递减即可

  • 遍历一次找到长度最短的字符串str[i],长度为length
  • 初始化公共前缀为str[i]
  • 开始进入循环直到length<=0
    • 如果前length个字符都相同则返回
    • 否则length减1

判断前length个字符是否相同可单独定义一个函数遍历来判断。

实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if len(strs) == 0:
return ''
length = len(strs[0])
for str in strs:
length = min(length, len(str))
while length > 0:
if isCommonPrefix(strs, length):
return strs[0][:length]
else:
length -= 1
return ''


def isCommonPrefix(strs, length):
commonPrefix = strs[0][:length]
for i in range(1, len(strs)):
if strs[i][:length] == commonPrefix:
continue
else:
return False
return True

其他方法

既然要依次遍历,也可以直接把字符串中的第一个字符串作为初始的最长公共字符串,然后从首字符开始依次判断

  • 将第一个字符串strs[0]作为初始字符
  • 从头开始依次遍历strs[0]每个字符
    • 和剩下的字符串中对应位置的字符进行对比
    • 直到跟某个字符串长度相等或者跟某个字符串对应位置字符不一致退出
    • 否则返回strs[0]

实现:

1
2
3
4
5
6
7
8
9
10
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if len(strs) == 0:
return ''
for i in range(0, len(strs[0])):
char = strs[0][i]
for j in range(1, len(strs)):
if len(strs[j]) == i or strs[j][i] != char:
return strs[0][:i]
return strs[0]

注意if len(strs[j]) == i or strs[j][i] != char:这条判断的前后顺序不可以颠倒,否则会有index溢出的报错。

如果大家有更好的方法,欢迎一起探讨。