leetcode - 最长公共前缀

leetcode: 最长公共前缀

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

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

首先，这一题的思路是从头到尾两辆比较，上一次比较的公共前缀用于下一次比较，代码如下：

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if strs == []:
            return ""
        else:
            s = strs[0]
            for i in range(1, len(strs)):
                temp = ""
                if strs[i] == "":
                    return ""
                else:
                    for j in range(min(len(strs[i]), len(s))):
                        if(strs[i][j] == s[j]):
                            temp += s[j]
                            if j == min(len(strs[i]), len(s)) - 1:
                                s = temp
                        else:
                            s = temp;
                            break;
            return s

可以看到，这个方法我们用了很多的特殊情况处理，比如只有空list，list中有空串等（一次次出错中补出来的= =）

评论中有一些启发的思路，比如说，字符串是可以比较大小的，那么不就可以直接只比较最大和最小的两项吗

代码如下

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        temp = ""
        if strs == []:          //也能写成if not strs
            return ""
        else:
            smax = max(strs)
            smin = min(strs)
            for i in range(min(len(smax), len(smin))):
                if smax[i] == smin[i]:
                    temp += smax[i]
                else:
                    break
        return temp

另外就是利用zip函数，把str对齐压缩然后去重，取最短的对象的函数特性正好可以利用到，在list中找到长度大于1前的就是公共前缀，有点神奇：

class Solution(object):
    def longestCommonPrefix(self, strs):
        if not strs: return ""
        ss = list(map(set, zip(*strs)))
        res = ""
        for i, x in enumerate(ss):
            x = list(x)
            if len(x) > 1:
                break
            res = res + x[0]
        return res

这是今天的份了。

今天雨有点大，鞋也湿了，头有点痛晚上还有实验。。。

心塞的看看桌上的老婆，发现双十一买不起新老婆

呵，男人