内容:
Write a function to find the longest common prefix string amongst an array of strings.
编写一个函数来查找字符串数组中最长的公共前缀字符串。
理解题目:
如数组 ["a", "b"] 最长的公共前缀字符串是 “”;
如数组 ["aa", "aa"] 最长的公共前缀字符串是 “aa”;
如数组 ["abc", "abcd"] 最长的公共前缀字符串是 “abc”。。。
1 1 如果数组为空,则最长公共前缀为"";
2
3 2 如果数组不为空:
4 (1)找出字符串数组中长度最短的字符串min,其长度为min_len; 因为最长的公共前缀长度不会超过min_len;
5 (2)遍历数组,将min位置为[i] 的字符 和 数组中其他字符串位置为[i]的字符 比较;
6 如果不相等,则最长公共前缀为 min的前i个字符;
7 如果都相等,则最长公共前缀为 min。
1 func longestCommonPrefix(strs []string) string {
2
3 if len(strs) == 0 {
4 return ""
5 }
6
7 min_len := len(strs[0])
8 index := 0
9 for i:=0; i<len(strs); i++ {
10 if len(strs[i]) < min_len {
11 min_len = len(strs[i])
12 index = i
13 }
14 }
15
16 for j:=0; j<len(strs[index]); j++ {
17 for k:=0; k<len(strs); k++ {
18 if strs[index][j] != strs[k][j]{
19 return strs[index][:j]
20 }
21 }
22 }
23 return strs[index]
24 }
看一下耗时:
1 class Solution:
2 def longestCommonPrefix(self, strs):
3 """
4 :type strs: List[str]
5 :rtype: str
6 """
7 if not strs:
8 return ""
9 shortstr = min(strs, key=len)
10 for i, cha in enumerate(shortstr):
11 for other in strs:
12 if other[i] != cha:
13 return shortstr[:i]
14 return shortstr
看一下耗时:
是不是感觉go要快很多,Python更优雅?