让我们一起啃算法----最长公共前缀

最长公共前缀(Longest-Common-Prefix)

题干如下:

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:所有输入只包含小写字母 a-z 。
来源:力扣

解题思路

首先我们从题干入手,求字符串数组的公共前缀,那么什么是公共前缀呢?其实就是所有字符串都有的子串,并且这个子串的位置还比较特殊,它在字符串的开始位置。

有了这个认知之后,我们随意取两个字符串 S1 和 S2,先得出 S1 和 S2 的公共前缀,记为 P1。如果没有公共前缀,那么直接返回空字符串,如果存在 P1,那么将 P1 和 S3 比较,得出公共前缀 P2,以此类推。( P1的长度一定是大于等于 P2 )。

至于如何求公共前缀 P,流程图如下:

代码实现

GO语言实现

func longestCommonPrefix(strs []string) string {
 if len(strs) <= 0 {
 return ""
 }
 // 将前缀初始化为第一个元素值
 var prefix = strs[0]
 for i := 1; i< len(strs); i++ {
 // 判断字符串是否是prefix开头的,如果是 strings.Index 返回 0
 if strings.Index(strs[i], prefix) != 0 {
 // 去掉前缀的最后一个字符
 prefix = prefix[:len(prefix)-1]
 // 因为会执行 i++,为了保证 i 不变,先 i--
 i--
 }
 }
 return prefix
}

总结

每天进步一点点,加油!
算法教程项目,每天更新一题,点个 star 支持一下呀:
https://github.com/wx-satellite/learning-algorithm

本文来自:Segmentfault

感谢作者:三斤和他的朋友们

查看原文:让我们一起啃算法----最长公共前缀

• 编辑
• 预览