最长公共前缀014 -力扣（py3+zip、set）

落日映苍穹つ 2022-12-19 11:40 144阅读 0赞

# 1. 题目描述 #

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

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

示例 1:

输入: \[“flower”,“flow”,“flight”\]  
输出: “fl”  
示例 2:

输入: \[“dog”,“racecar”,“car”\]  
输出: “”  
解释: 输入不存在公共前缀。  
说明:

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/longest-common-prefix

# 2. 解法 #

1.一个比较巧的解法，利用python3的内置函数zip，以及内置的数据结构类型set.

首先将list变为可变参数，放入zip函数中，zip函数将所有字符串中的每个字符组成一个tuple，关于zip函数的用法，可以参考[Python zip() 函数][Python zip_],再利用集合set的不可重复性，将每个tuple转化为set，若set中的元素为1个，则证明该元素是公共前缀。

def longestCommonPrefix(self, strs: List[str]) -> str:
            ans = ''
            for i in zip(*strs):
                if len(set(i)) == 1:
                    ans += i[0]
                else:
                    break
            return ans

2.横向扫描  
用  LCP ( S 1 … S n ) \\textit\{LCP\}(S\_1 \\ldots S\_n) LCP(S1…Sn)表示字符串  S 1 … S n S\_1 \\ldots S\_n S1…Sn的最长公共前缀。

可以得到以下结论：

LCP ( S 1 … S n ) = LCP ( LCP ( LCP ( S 1 , S 2 ) , S 3 ) , … S n ) \\textit\{LCP\}(S\_1 \\ldots S\_n) = \\textit\{LCP\}(\\textit\{LCP\}(\\textit\{LCP\}(S\_1, S\_2),S\_3),\\ldots S\_n) LCP(S1…Sn)=LCP(LCP(LCP(S1,S2),S3),…Sn)

基于该结论，可以得到一种查找字符串数组中的最长公共前缀的简单方法。依次遍历字符串数组中的每个字符串，对于每个遍历到的字符串，更新最长公共前缀，当遍历完所有的字符串以后，即可得到字符串数组中的最长公共前缀。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70_pic_center]  
如果在尚未遍历完所有的字符串时，最长公共前缀已经是空串，则最长公共前缀一定是空串，因此不需要继续遍历剩下的字符串，直接返回空串即可。  
该部分参考的官方给出的答案，解释的很到位。

def longestCommonPrefix4(self, strs):
        if not strs:
            return ''
        pre, count = strs[0], len(strs)
        for i in range(1, count):
            pre = self.prefix(pre, strs[i])
            if not pre:
                break
        return pre
    
    def prefix(self, str1, str2):
        count = len(str1)
        for i in range(count):
            if i == len(str2) or str1[i] != str2[i]:
                return str1[:i]
        return str1

3.纵向扫描  
这个方法我想是大部分人都可以想到的方法：

从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，如果相同则继续对下一列进行比较，如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70_pic_center 1]  
在具体实现时，可以通过选取字符串列表中的第一个字符串的长度作为循环的次数，在对字符串中的每个元素进行比较时，需要注意，一旦其中有一个字符串的长度等于当前循环的标识i，则停止循环，因为此时字符串的长度最大为i，后面再循环，会出现字符串的越界行为。

def longestCommonPrefix3(self, strs):
        if not strs:
            return ''
        count = len(strs[0])
        for i in range(0, count):
            if any(i == len(strs[j]) or strs[0][i] != strs[j][i] for j in range(1, len(strs))):
                return strs[0][:i]
        return strs[0]

时间复杂度：O(mn)，其中 m是字符串数组中的字符串的平均长度，n是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。

空间复杂度：O(1)。使用的额外空间复杂度为常数。

上面之所以需要注意字符串的越界行为是因为直接选择strs中的第一个字符串的长度作为循环次数，因为可能该字符串的长度并不为所有字符串长度的最小值，如果是最小值，那么就不必注意字符串的越界行为了。因此也可以先找到字符串数组中最短字符串的长度。

def longestCommonPrefix2(self, strs):
            if not strs:
                return ''
            count = min([len(strs[i]) for i in range(len(strs))])
            for i in range(0, count):
                if any(strs[0][i] != strs[j][i] for j in range(1, len(strs))):
                    return strs[0][:i]
            return strs[0]

在实际编写代码时可以利用python的列表生成式，享受python的独特魅力。

参考链接：https://leetcode-cn.com/problems/longest-common-prefix/solution/zui-chang-gong-gong-qian-zhui-by-leetcode-solution/

[Python zip_]: https://www.runoob.com/python/python-func-zip.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/fd3c80fe40a04b86a4d055833a15da21.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/26d817f7e2e842f1a4f50212dddcef74.png