What is the Longest Common Prefix problem?

The Longest Common Prefix problem asks you to find the longest prefix that all strings in a given array share. If no such prefix exists, return an empty string.

What is the most efficient approach to solving the Longest Common Prefix?

Vertical scanning is often the simplest and most efficient for small inputs, while divide and conquer is optimal for larger inputs. The choice depends on input size and constraints.

What are the edge cases for the Longest Common Prefix problem?

Edge cases include arrays with no common prefix, arrays with one string, arrays with empty strings, and strings with varying lengths.

How does the time complexity change with input size?

The time complexity of the solution depends on both the number of strings and the length of the shortest string, typically O(m * n) where m is the string length and n is the number of strings.

How do you handle inputs where some strings are empty?

If any string is empty, the result is immediately an empty string since there is no common prefix. This should be checked before processing the strings.

#14

Easy

auto_awesome数组·string

LeetCode 题解工作台

最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 "" 。示例 1：输入： strs = ["flower","flow","flight"] 输出： "fl" 示例 2：输入： strs = ["dog","racecar","car"] 输出： "" 解释：…

数组字符串字典树

题目描述

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

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

示例 1：

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

示例 2：

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

提示：

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

lightbulb

解题思路

方法一：字符比较

我们以第一个字符串 $strs[0]$ 为基准，依次比较后面的字符串的第 $i$ 个字符是否与 $strs[0]$ 的第 $i$ 个字符相同，如果相同则继续比较下一个字符，否则返回 $strs[0]$ 的前 $i$ 个字符。

遍历结束，说明所有字符串的前 $i$ 个字符都相同，返回 $strs[0]$ 即可。

时间复杂度 $(n \times m)$ ，其中 $n$ 和 $m$ 分别为字符串数组的长度以及字符串的最小长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        for i in range(len(strs[0])):
            for s in strs[1:]:
                if len(s) <= i or s[i] != strs[0][i]:
                    return s[:i]
        return strs[0]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you understand how to handle edge cases like when there is no common prefix?
question_mark
Can you describe the trade-offs between vertical scanning and horizontal scanning?
question_mark
Will you be able to choose the most efficient approach based on the input size?

warning

常见陷阱

外企场景

error
Failing to handle the case where no common prefix exists, returning an empty string instead of a valid result.
error
Not accounting for the possibility of empty strings in the input, which can break certain approaches if not handled carefully.
error
Incorrectly assuming that all strings must have a non-zero length; the edge case where an input array has an empty string should be checked.

swap_horiz

进阶变体

外企场景

arrow_right_alt
How would you optimize the solution for very large input sizes, say up to a million strings?
arrow_right_alt
Can you modify the solution to find the longest common suffix instead of the prefix?
arrow_right_alt
How would the problem change if strings could contain uppercase letters or other characters?

help

常见问题

外企场景

继续练习

#139 单词拆分 #140 单词拆分 II #212 单词搜索 II