LeetCode-14 - Longest Common Pre

Write a function to find the longest common prefix string amongst an array of strings.

Solution1

用第一个元素作为基准，每个元素都与第一个元素的前半部分作compare
算法复杂度为O(n2)

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if len(strs) == 0:
            return ""
        elif len(strs) == 1:
            return strs[0]
        else:
            count = 0
            while(True):
                for i in range(len(strs)):
                    try:
                        if not strs[i][count] == strs[0][count]:
                            return strs[0][:count]
                        else:
                            continue
                    except:
                        return strs[0][:count]
                count += 1

Solution2

将list中的每个元素的每个字符都分别zip在一起，然后透过set的len来看是否字符相等
算法复杂度为O(n)

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if len(strs) == 0:
            return ""

        for i, v in enumerate(zip(*strs)):
            if len(set(v)) > 1:
                return strs[0][:i]
        return strs[0]

反思

1. zip函数用得不够666
2. set可以除重，len(set)的用法很妙