14. 最长公共前缀
14. 最长公共前缀
14. 最长公共前缀
一、题目描述：
编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串 “”。 示例 1： 输入：strs = [“flower”,“flow”,“flight”] 输出：“fl” 示例 2： 输入：strs = [“dog”,“racecar”,“car”] 输出：“” 解释：输入不存在公共前缀。 提示： 1 <= strs.length <= 200 0 <= strs[i].length <= 200 strs[i] 仅由小写英文字母组成 来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/longest-common-prefix 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二、思路分析：
这道题考察了什么思想？你的思路是什么？
这道题目我的思路很简单，就是求字符串切片中最短的那个字符串的长度n，然后从1开始一直到n，截取前面几个字符判断是否一致，如若一致，即继续截取下一个，直到求出最长的公共前缀。
做题的时候是不是一次通过的，遇到了什么问题，需要注意什么细节？
不是，我的第一思路执行起来有点问题，需要多次遍历切片，时间复杂度太高了！
我们可以先求字符串切片中最前面两个字符串的最长公共前缀prefix, 之后遍历字符串数组strs时，迭代这个prefix就好了，即求prefix和下一个字符串strs[i]的最长公共前缀。特别的，如果循环中，prefix长度为0，说明strs[0:i]范围内的所有字符串最长公共前缀为空串，后续的遍历也就没有意义了，直接break退出循环。当然，还需要考虑特殊情况，如果字符串数组的长度为0，直接返回空串。
有几种解法，哪种解法时间复杂度最低，哪种解法空间复杂度最低，最优解法是什么？其他人的题解是什么，谁的效率更好一些？用不同语言实现的话，哪个语言速度最快？
func longestCommonPrefix(strs []string) string {
if len(strs) == 0 {
return ""
}
for i := 0; i < len(strs[0]); i++ {
for j := 1; j < len(strs); j++ {
if i == len(strs[j]) || strs[j][i] != strs[0][i] {
return strs[0][:i]
}
}
}
return strs[0]
}
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/longest-common-prefix/solution/zui-chang-gong-gong-qian-zhui-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。三、AC 代码：
func LongestCommonPrefix(strs []string) string {
count := len(strs)
if count == 0 {
return ""
}
prefix := strs[0]
for i := 1; i < count; i++ {
prefix = lcp(prefix, strs[i])
if len(prefix) == 0 {
break
}
}
return prefix
}
func lcp(str1, str2 string) string {
length := Min(len(str1), len(str2))
index := 0
for index < length && str1[index] == str2[index] {
index++
}
return str1[:index]
}
func Min(a, b int) int {
if a < b {
return a
}
return b
}四、总结：
这道题目如果要求时间复杂度不高的话，实现起来还是需要一点技巧的，我的第一思路太暴力了，时间复杂度太高，测试点复杂一点的话，肯定是过不去的！