20.最长公共前缀

题目

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

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

示例 1:

• 输入：strs = ["flower","flow","flight"]
• 输出："fl"

示例 2:

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

提示:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] 如果非空，则仅由小写英文字母组成

思路

遍历每次找重合的前缀部分

横向扫描，依次遍历每个字符串，更新最长公共前缀

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        ans = strs[0]
        def compare(s1, s2) -> str:
            result = ""
            for i in range(min(len(s1), len(s2))):
                if s1[i] == s2[i]:
                    result += s1[i]
                else:
                    break
            return result

        for i in range(1, len(strs)):
            ans = compare(ans, strs[i])
        return ans

最大的可能就是第一个元素的全部值，所以挨着遍历第一个元素的每个字符是否都匹配就可以:

class Solution {
    fun longestCommonPrefix(strs: Array<String>): String {
        val target = strs[0]
        for (i in 0..<target.length) {
            for (j in 1..<strs.size) {
                if (i >= strs[j].length || target[i] != strs[j][i]) {
                    return target.substring(0, i)
                }
            }
        }
        return target
    }
}

复杂度分析:

• 时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。

• 空间复杂度：O(1)。使用的额外空间复杂度为常数。

• 下一篇

• 邮箱 ：charon.chui@gmail.com
• Good Luck!