【Leetcode】【python】Longest Common Prefix 最长公共前缀

题目大意

寻找一组字符串的公共起始子串

解题思路

将每个字符串和第一个字符串对比,而且从第一个字母开始遍历,一旦出现某个字符串结束了,或者字母不同,则直接输出第一个字符串的前N个字母

代码

时间复杂度:O(n*k) k为结果字符串长度
空间复杂度:O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if not strs:
return ""
for i in range(len(strs[0])):
for string in strs[1:]: # flow, flight
if i >= len(string) or string[i] != strs[0][i]:
return strs[0][:i]
return strs[0]

总结