LeetCode--014--最长公共前缀

问题描述：

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"

示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明:

所有输入只包含小写字母 a-z 。

方法1:

　　贪心：将第一个串和第二个串进行比较，得出的最长前缀再与剩下的进行比较。（48ms）

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if len(strs)>1:
            
            s0 = strs[0]
            s1 = strs[1]
        elif len(strs) == 1:
            return strs[0]
        else:
            return ""
        common = ""
        flag = True
        i = 0
        while flag and i < len(s0) and i < len(s1):
            if s0[i] == s1[i]:
                common += s0[i]
            else:
                flag = False
            i += 1
        for i in range (2,len(strs)):
            c = strs[i]
            j = 0
            common2 = ""
            while j < len(c) and j < len(common):
                if c[j] == common[j]:
                    common2 += c[j]
                    j += 1
                else:
                    break
            common = common2
        return common

方法2（官方）：

　　利用min和max函数，找出List中最小值元素s1和最大值元素s2，纪录s1中和s2字符不相同时候的下标，进行截断处理。（24ms）

1 if not len(strs):
　 　return ''
3 s1 = min(strs)
s2 = max(strs)
for n, s in enumerate(s1):
　　if not s2[n] == s:
    　　return s1[:n]
return s1

注：enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中。

>>>seasons = ['Spring', 'Summer', 'Fall', 'Winter']
>>> list(enumerate(seasons))
[(0, 'Spring'), (1, 'Summer'), (2, 'Fall'), (3, 'Winter')]
>>> list(enumerate(seasons, start=1))       # 小标从 1 开始
[(1, 'Spring'), (2, 'Summer'), (3, 'Fall'), (4, 'Winter')]

>>>seq = ['one', 'two', 'three']
>>> for i, element in enumerate(seq):
...     print i, element
... 
0 one
1 two
2 three

方法3：

        ans = ""
        
        for i in zip(*strs):
            if  len(set(i)) > 1:
                return ans
            ans += i[0]
        
        return ans
    

例

strs=["flower","flgdcvghyf","fove"]
for i in zip(*strs):
     print(i)

>>
('f','f','f')
('l','l','o')
('o','g','v')
('w','d','e')

 

 

2018-07-22 11:18:24