jsp-basic

最长公共前缀

题目地址：最长公关前缀

题目描述

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

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

示例 1:

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

示例 2:

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

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

python中字符串有大小，例如：a<b<c; flight < flow < flower

思路

• $O(n^2)$: 找出最短的字符串，然后看所有字符串相同位置上的字符是否一样
• 找出最小和最大字符串，最小和最大字符串的最长公共前缀即整个list的最长公共前缀

代码

n方复杂度

def longestCommonPrefix(strs):
    if strs:
        # 按照字符串长度排序
        strs.sort(key=lambda i: len(i))
        first_str = strs[0]
        i = 0
        flag = True
        while i < len(first_str) and flag:
            s = first_str[i]
            for st in strs:
                if st[i] != s:
                    flag = False
            if flag:
                i += 1
        print(first_str[0:i])
        return first_str[0:i]
    else:
        return ""

n复杂度

def longestCommonPrefix2(strs):
    if not strs:
        return ""
    # 按字母表顺序：flight < flow <flower
    min_str = min(strs)
    max_str = max(strs)
    # 只需要找最小和最大字符串的最长公共前缀
    for i, x in enumerate(min_str):
        if x != max_str[i]:
            return min_str[:i]
    return min_str

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 changzeyan@foxmail.com