13
让我们一起啃算法----最长公共前缀
source link: https://studygolang.com/articles/28292
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
最长公共前缀（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
}
总结
欢迎关注我们的微信公众号，每天学习Go知识
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK