跳至主要內容

0014. 最长公共前缀

ITCharge大约 1 分钟

0014. 最长公共前缀open in new window

  • 标签:字典树、字符串
  • 难度:简单

题目链接

题目大意

描述:给定一个字符串数组 strs

要求:返回字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串 ""

说明

  • 1strs.length2001 \le strs.length \le 200
  • 0strs[i].length2000 \le strs[i].length \le 200
  • strs[i] 仅由小写英文字母组成。

示例

  • 示例 1:
输入:strs = ["flower","flow","flight"]
输出:"fl"
  • 示例 2:
输入:strs = ["dog","racecar","car"]
输出:""
解释:输入不存在公共前缀。

解题思路

思路 1:纵向遍历

  1. 依次遍历所有字符串的每一列,比较相同位置上的字符是否相同。
    1. 如果相同,则继续对下一列进行比较。
    2. 如果不相同,则当前列字母不再属于公共前缀,直接返回当前列之前的部分。
  2. 如果遍历结束,说明字符串数组中的所有字符串都相等,则可将字符串数组中的第一个字符串作为公共前缀进行返回。

思路 1:代码

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""

        length = len(strs[0])
        count = len(strs)
        for i in range(length):
            c = strs[0][i]
            for j in range(1, count):
                if len(strs[j]) == i or strs[j][i] != c:
                    return strs[0][:i]
        return strs[0]

思路 1:复杂度分析

  • 时间复杂度O(m×n)O(m \times n),其中 mm 是字符串数组中的字符串的平均长度,nn 是字符串的数量。
  • 空间复杂度O(1)O(1)