Leetcode题解 - 14. 最长公共前缀

🔗题目描述

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

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

🔗示例

示例 1:

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

示例 2:

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

🔗解题思路

🔗常规思路——递加法

取数组第1个元素，遍历字符，与剩余数组元素进行比较，碰到第一个不相同的元素或者长度越界时比较终止，详细说明两个终止条件：

若两个数组元素为flower和flowxr,遍历需要在e处停止；
遍历数组元素时，要判断是否越界，如flower和flow，遍历到e处就要停止（有的同学先找出数组中最短元素，再按最短元素遍历，完全没必要）。

然后考虑边界情况，如果数组元素为0则直接返回空，数组元素为1时，则直接返回此元素。

代码：

def longestCommonPrefix(self, strs: List[str]) -> str:
    if len(strs) == 0:
        return ""
    elif len(strs) == 1:
        return strs[0]
    result = ""
    for pos, cha in enumerate(strs[0], 0):
        is_common = False
        for j in range(1, len(strs)):
            # 「pos <= len(strs[j]) - 1」是防止越界
            if pos <= len(strs[j]) - 1 and cha == strs[j][pos]:
                is_common = True
            else:
                is_common = False
                break
        if is_common:
            result = result + cha
        else:
            break
    return result

此方法时间复杂度$O(n^2)$，空间复杂度为$O(1)$。

运行情况：

执行用时 :32 ms, 在所有 python3 提交中击败了99.52%的用户
内存消耗 :13.9 MB, 在所有 python3 提交中击败了5.53%的用户

🔗常规思路——递减法

与递加法相反，递减法是直接将第一个元素作为最长公共前缀，在其他元素中查找是否为其子串，若不是，则递减默认元素的后缀，直到找到子串。

代码：

def longestCommonPrefix(self, strs: List[str]) -> str:
    if len(strs) == 0:
        return ""
    elif len(strs) == 1:
        return strs[0]
    prefix = strs[0]
    for i in range(len(strs)):
        # 如果不是下一个元素的子串，则减少一个后缀
        while 0 != strs[i].find(prefix):
            prefix = prefix[:-1]
            if not prefix:
                return ""
    return prefix

运行情况：

执行用时 :56 ms, 在所有 python3 提交中击败了33.32%的用户
内存消耗 :13.9 MB, 在所有 python3 提交中击败了5.53%的用户

🔗python标准库解法

os包的os.path.commonprefix()函数可以直接返回list中的最长公共前缀，其实现为：

def longestCommonPrefix(self, strs: List[str]) -> str:
    if len(strs) == 0:
        return ""
    elif len(strs) == 1:
        return strs[0]
    # 以下为python标准库代码
    s1 = min(strs)
    s2 = max(strs)
    for i, c in enumerate(s1):
        if c != s2[i]:
            return s1[:i]
    return s1

通过min()和max()函数找出list中的最「大」元素和最「小」元素，python中字符串的「大小」比较是根据每个相对于位置字母的ASCII码比较的，如f的ASCII码为102，数值的大小可以通过ASCII码表查询，也可以通过python的ord(str)函数查看。

然后遍历较「小」的字符串，在第一次出现相对于位置的字符不同时终止，从起始位置到此处之前的字符串即为最长公共子串。

此方法算是递减法的黑科技实现。

🔗黑魔法解法

zip()函数是将多个list的对应元素打包为一个个的Tuple，返回一个可迭代的对象，长度为最短长度的list。如：

a = [1,2]
b = [1,2,3]
# list(zip(a,b))为[(1, 1), (2, 2)]

而zip(*)与zip()相反，是将list解压，如：

a = ["12","345"]
# list(zip(*a))为[('1', '2'), ('3', '4')]

set()函数是从一个可迭代的对象的元素中创建一个无序不重复的元素集（即set类型），经过一一对应地解压，再通过创建set类型的过滤，若前缀相同则set对象长度一定为1，因此有以下代码：

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