14. 最长公共前缀

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

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

示例 1:

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

示例 2:

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

说明:

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

思路一：横向扫描

首先假定最长公共前缀初始化为predix = strs[0],
从下标为1的字符串开始遍历 ，依次计算二者的最长公共前缀，并更新predix= lcp(predix, strs[i])
当遍历所有字符串之后，就得到了最长公共前缀的值
当尚未遍历完字符串的时候，最长公共字符串的值已经是空串，则最长公共字符串就是空串，可以直接返回空串，不需要继续遍历剩余字符串了。详细过程看下图

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

python3代码实现---横向扫描

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs: return ''
        predix = strs[0]
        def lcp(str1, str2):
            index, minlen = 0, min(len(str1),len(str2))
            while index < minlen and str1[index] == str2[index]:
                index += 1
            return str1[:index]
        for i in range(1, len(strs)):
            predix = lcp(predix, strs[i])
            if not predix:
                break
        return predix

思路二：纵向扫描

纵向扫描时，按照索引从前向后扫描，依次比较相同索引位置上的字符是否相同：
如果相同则继续扫描下一个索引位置；
如果不相同，则当前索引位置已经不再属于公共前缀，那么从0到前一个索引的部分为最长公共前缀；
同时还要判断，某一个字符串是否已经扫描完成，如果有字符串较短，已经扫描完了，则其他字符串也不需要再进行扫描。

image.png

python3代码实现---纵向扫描

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs: return ''
        length = len(strs[0])
        strcount = len(strs)
        for i in range(length):
            c = strs[0][i]
            for j in range(1, strcount):
                if i == len(strs[j]) or strs[j][i] != c:
                    return strs[0][:i]
        return strs[0]

思路三之利用zip

首先我们可以看下zip函数的用法和效果

nums = ['flower','flow','flight']
for i in zip(*nums):print(i)

其结果如下，那么只需要将元祖一次放入set集合中，如果元祖内元素内容都相同，那么就添加到结果集中。

('f', 'f', 'f')
('l', 'l', 'l')
('o', 'o', 'i')
('w', 'w', 'g')

python3解法之利用zip，代码实现如下：

class Solution:
    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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-common-prefix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。