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

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、思路分析：

1. 这道题考察了什么思想？你的思路是什么？

   这道题目我的思路很简单，就是求字符串切片中最短的那个字符串的长度n，然后从1开始一直到n，截取前面几个字符判断是否一致，如若一致，即继续截取下一个，直到求出最长的公共前缀。

2. 做题的时候是不是一次通过的，遇到了什么问题，需要注意什么细节？

   不是，我的第一思路执行起来有点问题，需要多次遍历切片，时间复杂度太高了！

   我们可以先求字符串切片中最前面两个字符串的最长公共前缀prefix, 之后遍历字符串数组strs时，迭代这个prefix就好了，即求prefix和下一个字符串strs[i]的最长公共前缀。特别的，如果循环中，prefix长度为0，说明strs[0:i]范围内的所有字符串最长公共前缀为空串，后续的遍历也就没有意义了，直接break退出循环。当然，还需要考虑特殊情况，如果字符串数组的长度为0，直接返回空串。

3. 有几种解法，哪种解法时间复杂度最低，哪种解法空间复杂度最低，最优解法是什么？其他人的题解是什么，谁的效率更好一些？用不同语言实现的话，哪个语言速度最快？

   

   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 := 0for index < length && str1[index] == str2[index] {index++}return str1[:index]
}func Min(a, b int) int {if a < b {return a}return b
}

四、总结：

这道题目如果要求时间复杂度不高的话，实现起来还是需要一点技巧的，我的第一思路太暴力了，时间复杂度太高，测试点复杂一点的话，肯定是过不去的！