forked from algorhythms/LeetCode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
015 Longest Common Prefix.py
42 lines (34 loc) · 1.01 KB
/
015 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
"""
Write a function to find the longest common prefix string amongst an array of strings.
"""
__author__ = 'Danyang'
class Solution:
def longestCommonPrefix(self, strs):
"""
O(k*n)
:param strs: a list of string
:return: string, prefix
"""
# checking, otherwise: ValueError: min() arg is an empty sequence
if not strs:
return ""
n = len(strs)
str_builder = ""
min_len = min(len(string) for string in strs)
for i in range(min_len):
char = strs[0][i]
j = 0
while j<n:
try:
if strs[j][i]!=char: break
j += 1
except IndexError:
break
if j==n:
str_builder += char
else:
break
return str_builder
if __name__=="__main__":
strs = ["abc", "abcd"]
print Solution().longestCommonPrefix(strs)