Leetcode 最长公共前缀

逃离我推掉我的手 2022-04-03 06:07 241阅读 0赞

题目：

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

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

**示例 1:**

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

**示例 2:**

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

**说明:**

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

方法一：  
class Solution(object):  
    def longestCommonPrefix(self, strs):  
        """  
        :type strs: List\[str\]  
        :rtype: str  
        """  
        if len(strs)==0:  
            return ""  
        prefix = strs\[0\]  
        for i in range(len(strs)):  
            \#找不到前缀时，从后往前裁剪前缀字符串  
            while strs\[i\].find(prefix)!=0:  
                prefix = prefix\[0:-1\]  
        return prefix

思路：

由于是公共前缀，它存在于每一个字串中，将他的初始值设为第一个字串，然后再逐步地从后往前裁剪成我们要的前缀。

方法就是遍历strs列表里的每一个字串，用 find 方法判断前缀是否在当前字串中，如果不在，说明前缀太长了，需要修剪。我们通过切片去掉前缀字串的最后一个字符，然后再次判断（内层while循环），循环直到前缀存在于当前字串里。

对列表里每个字串都作这样的检查（外层循环），就可以确定prefix是最长公共前缀了。

这是借鉴leetcode官网的解答，平均24ms。

方法二：

class Solution(object):  
    def longestCommonPrefix(self, strs):  
        if strs == \[\]: return ""  
        \# 找到最短的字符串  
        minLen, n = len(strs\[0\]), len(strs)  
        p = 0  
        for i in range(n):  
            length = len(strs\[i\])  
            if length < minLen:  
                minLen, p = length, i  
         \#公共字符逐个加入字串里        
        str1 = strs\[p\]  
        m = len(str1)  
        prefix = ''  
        for i in range(m):  
            char = str1\[i\]  
            for j in range(n):  
                if char != strs\[j\]\[i\]:  
                    return prefix  
            if j == n-1:  
                prefix += char  
        return prefix

思路：

先通过遍历找出最短的字串，它的下标记录为p。遍历这个字串的每一个字符，判断它是否也存在于列表里其他的字串的相同位置，如果存在则加入prefix；如果不存在，说明从这个字符开始就不是公共前缀了，此时直接返回即可。