最长公共前缀
题目链接: https://leetcode.cn/problems/longest-common-prefix/
题目描述
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""。
示例 1:
输入:strs = ["flower","flow","flight"]
输出:"fl"
示例 2:
输入:strs = ["dog","racecar","car"]
输出:""
解释:输入不存在公共前缀。
提示:
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成
解题思路:
以第一个元素为默认前缀,遍历所有元素,对每个元素的字符从前往后进行遍历,并与前缀进行对比
若字符与前缀中相同位置的字符不想等,则缩减前缀,并退出循环,对下一个元素进行遍历
func longestCommonPrefix(strs []string) string {
if len(strs) == 0 {
return ""
}
prefix := strs[0]
for i := 1; i < len(strs); i++ {
str := strs[i]
for j := 0; j < len(str) && j < len(prefix); j++ {
if str[j] != prefix[j] {
prefix = prefix[:j]
break
}
}
if len(str) < len(prefix) {
prefix = str
}
}
return prefix
}
复杂度分析
时间复杂度:
空间复杂度:
最后更新于
这有帮助吗?