最长公共前缀

难度简单

描述

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

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

示例 1

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

输出:"fl"

示例 2

输入:["dog", "racecar", "car"]

输出:""

题解

利用集合的思想,把数组中所有字符串同索引的字符放到集合中,最终集合长度是 1,说明一致,将字符追加到结果中,按照索引依此规则判断,直到集合长度不为 1 时返回结果。

实现

// TODO: 添加
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:     
        s = ""
        for i in zip(*strs):
            if len(set(i))==1:
                s += i[0]
            else:
                break           
        return s

复杂度分析

  • 时间复杂度:O(m \times n)

    m 是字符串数组的元素个数, n 是所有字符串中长度最小字符串的字符个数

  • 空间复杂度:O(1)