-
Notifications
You must be signed in to change notification settings - Fork 4
/
longest_common_prefix.py
64 lines (48 loc) · 1.35 KB
/
longest_common_prefix.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
"""
14. 最长公共前缀
字符串
简单
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""。
示例 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.com/problems/longest-common-prefix
"""
from typing import List
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
s_len = len(strs)
if s_len == 0:
return ''
min_len = min([len(s) for s in strs])
prefix_i = -1
stop = False
for i in range(min_len):
for j in range(s_len-1):
if strs[j][i] != strs[j+1][i]:
stop = True
break
if stop:
break
prefix_i = i
return strs[0][:prefix_i+1]
if __name__ == '__main__':
solution = Solution()
result = solution.longestCommonPrefix(["flower", "flow", "flight"])
print(result)
assert result == 'fl'
result = solution.longestCommonPrefix(["dog", "racecar", "car"])
print(result)
assert result == ''