题目内容
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"示例 2:
输入: ["dog","racecar","car"]
输出: ""解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。
方法一: 横向扫描
依次遍历字符串数组中的每个字符串，对于每个遍历到的字符串，更新最长公共前缀，当遍历完所有的字符串以后，即可得到字符串数组中的最长公共前缀。
说人话就是我们直接一个一个的比，先获取第一个和第二个的相同前缀，然后我们拿这个相同的前缀和第三个比最后依次比完，得到最长的公共前缀
示例代码：
package main
import "log"
func longestCommonPrefix(strs []string) string {
if len(strs) == 0 {
return ""
}
prefix := strs[0]
count := len(strs)
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(x, y int) int {
if x < y {
return x
}
return y
}
func main() {
text := longestCommonPrefix([]string{"ab", "abc", "ad"})
log.Println(text)
}
方法二：纵向扫描
纵向扫描时，从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，如果相同则继续对下一列进行比较，如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。
纵向扫描更简单，就是直接遍历所有的字符串，然后从第一位开始比较，如果发现不同的那么就直接退出
参考代码：
package main
import "log"
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]
}
func main() {
text := longestCommonPrefix([]string{"ab", "abc", "ad"})
log.Println(text)
}
方法三： 分治法
这个方法看起来不明所以，实际上就是利用了递归的思想，比对这么多很麻烦，我们就把这这个数组分成两部分，这里两部分继续细分，直到只剩下两个字符串为止，这样我们就可以直接比对这两个字符串，返回结果，然后再递归回去。。
首先我们看代码，先找中值，然后这里再调用自己本身获取左边的值和右边的值，我们这里先不管递归，这里执行完毕后会只返回左边的字符串和右边的字符串，最后我们只需要找到这两个字符串的公共前缀就可以了。
参考代码
package main
import "log"
func longestCommonPrefix(strs []string) string {
if len(strs) == 0 {
return ""
}
var lcp func(int, int) string
lcp = func(start, end int) string {
if start == end {
return strs[start]
}
mid := (start + end) / 2
lcpLeft, lcpRight := lcp(start, mid), lcp(mid+1, end)
minLength := min(len(lcpLeft), len(lcpRight))
for i := 0; i < minLength; i++ {
if lcpLeft[i] != lcpRight[i] {
return lcpLeft[:i]
}
}
return lcpLeft[:minLength]
}
return lcp(0, len(strs)-1)
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
func main() {
text := longestCommonPrefix([]string{"ab", "abc", "abdd"})
log.Println(text)
}
方法四： 二分查找
首先最重要的就是找到最短的那个字符串，找到之后我们就可以开始比较了，通过一个low和height来比较，low为0，height为最短字符串长度，我们先取中间值，然后比对所有字符串，判断这个前缀是否相等，如果相等那么low就等于中间值，然后再取low和height的中间值，如果不相等，那么就说明前缀要比中间值小，我们的height就直接设置为中值减一，直到low等于height就说明找到最短前缀了
package main
import "log"
func longestCommonPrefix(strs []string) string {
// 如果数组长度为0，那么直接返回空
if len(strs) == 0 {
return ""
}
// 这个函数用于判断指定长度下所有的字符数组的前缀是否相等
isCommonPrefix := func(length int) bool {
str0, count := strs[0][:length], len(strs)
for i := 1; i < count; i++ {
if strs[i][:length] != str0 {
return false
}
}
return true
}
// 首先我们假设距离最短的就是列表的第一个值
minLength := len(strs[0])
// 这里我们通过遍历，获取到最短字符串的长度
for _, s := range strs {
if len(s) < minLength {
minLength = len(s)
}
}
low, high := 0, minLength
// 这里我们通过low和height来判断最长的公共前缀，当low等于height的时候，就说明已经找到了
for low < high {
// 这里我们先取中值
mid := (high-low+1)/2 + low
// 判断中值的前缀是否相等，相等的话就说明最长的公共前缀肯定大于mid，我们可以把low增加
if isCommonPrefix(mid) {
low = mid
} else {
// 这里就说明中值的前缀不相等，我们这里的height就可以比low小一个，然后我们再继续比较
high = mid - 1
}
}
return strs[0][:low]
}
func main() {
text := longestCommonPrefix([]string{"ab", "abc", "abdd"})
log.Println(text)
}
