14.最长公共前缀.md

14. 最长公共前缀

https://leetcode-cn.com/problems/longest-common-prefix/

难度：简单

题目：

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

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

示例：

示例 1：

输入：strs = ["flower","flow","flight"]

输出："fl"

示例 2：

输入：strs = ["dog","racecar","car"]

输出：""

解释：输入不存在公共前缀。

分析

只要你熟悉zip方法的使用，这种题简直是塞牙缝的...当然除去简化方法，再提供其他几种思路。

内置函数zip解题：

使用内置的zip函数进行纵向合并，即可快速解题。

class Solution:
    def longestCommonPrefix(self, strs):
        ret = ''
        for i in zip(*strs):
            if len(set(i)) == 1:
                ret += i[0]
            else:
                break
        return ret

基本的纵向查找

本身通过while 循环和条件判断，无需求最小长度，但这样写起来更为简洁一下。

class Solution(object):
    def longestCommonPrefix(self, strs):
        min_len = min(len(i) for i in strs)
        ret = ""
        for i in range(min_len):
            if len(set(s[i] for s in strs)) > 1:
                break
            ret += strs[0][i]
        return ret

字符串排序

字符串本身按位排序后，只需要针对第一个和最后一个字符串进行比较就能获取最终答案。 相比于纵向查找，看似只比较了第一个和最后一个，但是排序也是消耗时间的...

class Solution(object):
    def longestCommonPrefix(self, strs):
        strs.sort()
        lg = min(len(strs[0]), len(strs[-1]))
        ret = ""
        for i in range(lg):
            if strs[0][i] != strs[-1][i]:
                break
            ret += strs[0][i]
        return ret

前缀树(字典树)

其实这道题如果做过前缀树的题目，应该都了解这种解法很符合该题，但大家估计都觉得有些麻烦，所以没写出来吧，在这里提供下前缀树的解题.

1. 首先我们将每个单词追加至字典树中，这里要注意，每个单词在结束时需要追加end，下面说为何。
2. 执行1后，我们随机取一个单词(默认就拿一个吧)
3. 执行search的方法，如果字典树中某个节点额长度大于1，表示在此处遇到了分支，需要终止
4. 那么end有什么用？比如['a','ab']，如果只比较3的条件，结果就成了"ab"，所以需要同时判断是否在该节点出现了某个单词的终止情况。

前缀树的经典题目参照： 208.实现Trie(前缀树)

这里使用字典树看效率就知道了有些过了...

class Trie:
    def __init__(self):
        self.dic = {}

    def insert(self, word):
        tmp = self.dic
        for w in word:
            if w not in tmp:
                tmp[w] = {}
            tmp = tmp[w]
        tmp['end'] = True

    def search(self, word):
        ret = ''
        tmp = self.dic
        for w in word:
            if len(tmp) > 1 or tmp.get('end'):
                return ret
            if w in tmp:
                ret += w
            tmp = tmp[w]
        return ret


class Solution(object):
    def longestCommonPrefix(self, strs):
        trie = Trie()
        for s in strs:
            trie.insert(s)
        return trie.search(strs[0])

欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。

有喜欢力扣刷题的小伙伴可以加我微信（King_Uranus）互相鼓励，共同进步，一起玩转超级码力！

我的个人博客：https://qingfengpython.cn

力扣解题合集：https://github.com/BreezePython/AlgorithmMarkdown