0014. 最长公共前缀 #
- 标签:字符串
- 难度:简单
题目大意 #
描述:给定一个字符串数组 strs
。
要求:返回字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串 ""
。
说明:
- $1 \le strs.length \le 200$。
- $0 \le strs[i].length \le 200$。
strs[i]
仅由小写英文字母组成。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:纵向遍历 #
- 依次遍历所有字符串的每一列,比较相同位置上的字符是否相同。
- 如果相同,则继续对下一列进行比较。
- 如果不相同,则当前列字母不再属于公共前缀,直接返回当前列之前的部分。
- 如果遍历结束,说明字符串数组中的所有字符串都相等,则可将字符串数组中的第一个字符串作为公共前缀进行返回。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(m \times n)$,其中 $m$ 是字符串数组中的字符串的平均长度,$n$ 是字符串的数量。
- 空间复杂度:$O(1)$。