14.最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明：所有输入只包含小写字母 a-z 。
两个方法，思路详见注释。
1 class Solution(object):
2 def longestCommonPrefix(self, strs):
3 """
4 :type strs: List[str]
5 :rtype: str
6 """
7 if not strs:
8 return ""
9 length = len(strs) # 取得list的长度
10 if length == 1:
11 print(strs[0])
12 return strs[0]
13
14 strs.sort(key=len) # 根据列表中的字符串长度排序
15 ans = '' # 返回值
16 for i in range(len(strs[0])): # 以列表中长度最小的单词为基准进行遍历
17 for j in strs: # 遍历列表中的每个字符串
18 if j[i] != strs[0][i]: # 如果列表中的字符串的对应下标是否相同
19 return ans
20 else:
21 ans += strs[0][i] # 如果所有字符串下标都相同，更新最长公共前缀
22 return ans
23
24 def longestCommonPrefix2(self, strs):
25 """
26 :type strs: List[str]
27 :rtype: str
28 """
29 if not strs:
30 return ""
31
32 length = len(strs) # 取得list的长度
33 # print("list长度：", length)
34 if length == 1:
35 print(strs[0])
36 return strs[0]
37
38 ans = ""
39 ans = Solution().commonPrefix(strs[0], strs[1])
40 i = 1
41 if i == length:
42 print(ans)
43 return ans
44 else:
45 ans = Solution().commonPrefix(ans, strs[i])
46 # print(ans)
47 i += 1
48 print(ans)
49
50 # 比较两个字符串的最长前缀
51 def commonPrefix(self, str0, str1):
52 if str0 == '': return str1
53 if str1 == '': return str0
54 if str0 == str1: return str0
55 len0=len(str0)
56 len1=len(str1)
57 h = min(len0, len1)
58 ans = ''
59 i = 0
60 j = 0
61 # for k in range(length):
62 if str0[i] == str1[j]:
63 ans += str0[i]
64 i += 1
65 j += 1
66 else:
67 return ans