14. 最长公共前缀

发表于 分类于 阅读次数： 本文字数： 516 阅读时长 ≈ 2 分钟

这个题目要求，编写一个函数，查找输入的字符串数组的元素的最长公共前缀。所有的元素都是由小写字母组成的。

这个题目，初一看，就是一个两重循环的遍历算法。每个字符串的每个字母，一个一个比较过来就可以了，最自然的算法就是，第一个字符串的第一个字母，和第二个字符串的第一个字母，……，一直到最后，如果都一样，就找到了第一个前缀字母，以此类推，一旦遇到一个不一样的，循环就结束了。

这个算法两重循环，显然复杂度是字符串的长度乘以字符串的个数 O(mn)。我写出了这样的算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        l = len(strs)
        if l == 0 :
            return ""
        if l == 1 :
            return strs[0]
        common = ""
        for i in range(len(strs[0])):
            for j in range (len(strs)) :
                if i >= len(strs[j]) or strs[j][i] != strs[0][i] :
                    return common
            common += strs[0][i]
        return common

这个算法是正确的，已经被 Accept 了。我看了题解，我这个叫纵向比较，还可以横向比较，就是前两个串的最长公共串，再去和第三个比较，计算公共串，一直计算到最后一个。叫横向比较。

看到横向比较的算法，我就很容易发现这个题目的递归结构，这个问题可以递归解决的。N 个字符串的最长公共前缀，是 N - 1 个字符串的最长公共前缀和最后一个字符串的公共前缀。于是我们可以写个递归算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        l = len(strs)
        if l == 0 :
            return ""
        if l == 1 :
            return strs[0]
        common = ""
        sub = self.longestCommonPrefix(strs[1::])
        for i in range(len(sub)):
            if i >= len(strs[0]) or strs[0][i] != sub[i]:
                return common
            common += sub[i]
        return common

这个算法也是正确的，但是并没有更简洁一点 [捂脸笑着洒泪…… 就是意识到这个问题是递归结构的，就尝试一下写出其递归的算法，递归算法的时间复杂度，并不会更优秀，这个题目的问题在于，最小化子问题的解决编写起来和遍历解决，并没有什么显著的差异，所以递归算法并不显得简洁。仅作为一种练习吧。

知识点：

  1. 递归思想
  2. Python 的类方法怎么递归，需要使用 self 才能递归调用