14. 最长公共前缀

佚名 6年前 (2019-05-06) 随笔 1284人围观抢沙发百度已收录

题目：

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

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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

示例 1:

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

说明:

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

思路：既然给我的是字符串数组，那我要比较的就不是两个元素了，所以考虑把这些元素的元素都一个一个取出来，放进空字符串里面，然后用字符串的count方法数是不是l个，不是就退出，是就把这个元素存进答案字符串里面，记住每一次循环后，字符串要还原为空字符串。另外，需要做初始准备工作，为了避免越界情况，先找出这些字符串最短的那个，进行这个长度的循环取出。

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if(strs==[]):
            return ''
        l=len(strs)
        a=''
        ans=' '
        min=len(strs[0])
        for j in range(l):
            ml=len(strs[j])
            if(min>ml):
                min=ml
        for b in range(min):
            for i in range(l):
                a+=strs[i][b]
            if(a.count(strs[0][b])!=l):
                break
            ans+=strs[0][b]
            a=''
        answer=ans.lstrip()
        return answer

这里为什么用answer去获取呢。。。因为lstrip是返回值而不是更改原字符串。。

另外两个空字符串不能都命名，所以一个用了带空格的，因为python会指向同一个对象。。

执行用时 : 56 ms, 在Longest Common Prefix的Python3提交中击败了70.16% 的用户内存消耗 : 13.1 MB, 在Longest Common Prefix的Python3提交中击败了78.41% 的用户学习一下别人的方法：利用python的max()和min()，在Python里字符串是可以比较的，按照ascII值排，举例abb， aba，abac，最大为abb，最小为aba。所以只需要比较最大最小的公共前缀就是整个数组的公共前缀

    def longestCommonPrefix(self, strs):
        if not strs: return ""
        s1 = min(strs)
        s2 = max(strs)
        for i,x in enumerate(s1):
            if x != s2[i]:
                return s2[:i]
        return s1