for
循环将所有的字符串的数量放到一个数组里,然后很容易求得最小的字符串的字符数目。下一步就是通过两个for
循环,一步一步对比这b
个字符串之间的第a
个字符的字符是否相同,只要当前这第a
个字符都相同,就数目p
加一,最后返回strs[0][:p]
。
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if len(strs) == 0:
return ""
if len(strs) == 1:
return strs[0]
p = 0
nums = []
lens = len(strs)
for i in strs:
nums.append(len(i))
mini = min(nums)
for a in range(mini):
for b in range(lens-1):
if strs[b][a] != strs[b+1][a]:
break
else:
p += 1
continue
break
return strs[0][:p]
第二种:通过学习了别的大佬的方法,这里有一个我觉得挺不错的方法。主要很好的地方是用到了find()
方法,这个方法使我们的代码变得精简了许多。开始我们随便选一个strs
中的字符串然后赋给front
,最后我们对每个字符串依次都用find(front)
,如果说这个front
在当前这一个字符串里边(如果不在,会返回-1
),且front
在这个字符串的位置是从0
开始,那我们就到继续检验下一个字符串。如果说不在,则说明这个字符串有的字符不在这个字符串里,那么我们就从尾开始减少字符,直到front
的所有字符都在当前字符串中,且位置为0
,然后再同样的步骤开始检验下一个字符串。最后全部检验完成,剩余的front
就是我们要求的最长公共前缀。
时间复杂度:O(N^2)
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ""
front = strs[0]
for i in range(len(strs)):
while strs[i].find(front) != 0:
front = front[:-1]
return front
第三种:这里分享一个特别厉害的方法。用到了python的zio()
函数和set()
函数,详细的函数意义可以点击超链接。这个方法先是用zip(*strs)
将 strs
中所有字符串并列到迭代器中,逐次并列返回 strs
中所有字符串的第 1、2、3、…… 个字符,最后得到的各字符串的同一列字符放入set()
中,因为set()
不会储存重复的元素,所以如果所有字符都是相同的则会返回1
,所以就说明当前字符在所有字符串的位置都是一样的,那么就将这个字符放进front
中保存。后面的循环都是如此,最后直到出现有不同的字符,或者全部元素都被检验完,就break
出循环,然后返回保存好了重复前缀的front
。
时间复杂度:O(N^2)
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
front = ""
for i in zip(*strs):
if len(set(i)) == 1:
front += i[0]
else:
break
return front