leetcode【14题】Longest Common Prefix

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