最长公共前缀

- 日理万妓 2021-10-30 00:46 321阅读 0赞

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

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

示例 1:
    
    输入: ["flower","flow","flight"]
    输出: "fl"
    示例 2:
    
    输入: ["dog","racecar","car"]
    输出: ""
    解释: 输入不存在公共前缀。
    说明:

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

python3 zip()函数  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NDQ3J1bm5lcg_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20190818215824851.png]

**思路 1：**  
Python 特性，取每一个单词的同一位置的字母，看是否相同。

**思路 2：**  
取一个单词 s，和后面单词比较，看 s 与每个单词相同的最长前缀是多少！遍历所有单词

**思路 3：**  
按字典排序数组，比较第一个，和最后一个单词，有多少前缀相同。

代码:  
思路一：

class Solution:
        def longestCommonPrefix(self, strs):
            """
            :type strs: List[str]
            :rtype: str
            """
            res = ""
            for tmp in zip(*strs):
                tmp_set = set(tmp) # f,f,f
                if len(tmp_set) == 1:
                    res += tmp[0]  #存入
                else:
                    break
            return res

思路二：

class Solution:
        def longestCommonPrefix(self, s: List[str]) -> str:
            if not s:
                return ""
            res = s[0]  #取到第一个单词
            i = 1
            while i < len(s):  # len(s)为所有单词的个数
                while s[i].find(res) != 0:
                    res = res[0:len(res)-1]  #缩小res的前缀长度
                i += 1
            return res

思路三：

class Solution:
        def longestCommonPrefix(self, s: List[str]) -> str:
            if not s:
                return ""
            s.sort()
            n = len(s)
            a = s[0]
            b = s[n-1]
            res = ""
            for i in range(len(a)):
                if i < len(b) and a[i] == b[i]:
                    res += a[i]
                else:
                    break
            return res

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NDQ3J1bm5lcg_size_16_color_FFFFFF_t_70]: /images/20211029/17dd1effd51e4489af13b1ac91027531.png
[20190818215824851.png]: /images/20211029/6eb93e4741b343dd9db6ec716f3baa59.png