01
题目分析
题目14: 编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,则返回""
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。
我们要寻找最长公共前缀,那么首先这个前缀是公共的,所以我们可以从任意一个元素中找到它。假定我们现在就从第一个元素中寻找最长公共前缀。那么首先,我们可以将第一个元素设置为基准元素x0。假如数组为["flow","flower","flight"],flow就是我们的基准元素。
然后我们只需要依次将基准元素和后面的元素进行比较(假定后面的元素依次为x1,x2,x3....),不断更新基准元素,直到基准元素和所有元素都满足最长公共前缀的条件,就可以得到最长公共前缀。
具体比对过程如下:
如下图所示:
我们需要注意的是,在处理基准元素的过程中,如果基准元素和任一一个元素无法匹配,则说明不存在最长公共元素。
最后,我们记得处理一下临界条件。如果给定数组是空,也说明没有最长公共元素。
然后我们就可以开始写我们的代码了。
02
题目解答
func longestCommonPrefix(strs []string) string {
if len(strs) < 1 {
return ""
}
prefix := strs[0]
for _,k := range strs {
for strings.Index(k,prefix) != 0 {
if len(prefix) == 0 {
return ""
}
prefix = prefix[:len(prefix) - 1]
}
}
return prefix
}
注:本系列所有教程中都不会用到复杂的语言特性,大家不需要担心没有学过go。算法思想最重要,使用go纯属本人爱好。同时,本系列所有代码均在leetcode上进行过测试运行,保证其严谨性!
当然,我们也可以用分治法或者其他方法来解答这道题目。你可以自己尝试尝试哈。我们下期见!