问题
https://leetcode-cn.com/problems/longest-common-prefix
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ”“。
示例 1:
输入: [“flower”,”flow”,”flight”]
输出: “fl”
示例 2:
输入: [“dog”,”racecar”,”car”]
输出: “”
解释: 输入不存在公共前缀。
说明: 所有输入只包含小写字母 a-z 。
解法
这是一个 easy 的题目，自己做出来了，但看到题解后发现原来还有很多清奇思路。
横向比较
用 LCP(S1,S2...Sn) 表示字符串 S1,S2...Sn 的最长公共前缀，那么一定有 LCP(S1,S2...Sn)=LCP(LCP(LCP(S1,S2),S3),…Sn)。可以先让第一个字符串作为公共前缀，和第二个比较得到一个公共前缀，用这个新公共前缀和第三个字符串比较得到一个新的公共前缀……一直到公共前缀为空或比较完最后一个字符串。公共前缀在比较过程中会越来越小。
有几种情况需要处理：
- 字符串数组为空
- 字符串数组只有1个字符串
- 公共前缀为空串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
package main
import (
"fmt"
"math"
)
func longestCommonPrefix(data *[]string) string {
if data == nil || len(*data) == 0 {
return ""
}
if len(*data) == 1 {
return (*data)[0]
}
lcp := (*data)[0]
for i := 1; i < len(*data); i++ {
lcp = getCommonPrefix(&lcp, &(*data)[i])
if lcp == "" {
return lcp
}
}
return lcp
}
func getCommonPrefix(s1, s2 *string) string {
minLen := int(math.Min(float64(len(*s1)), float64(len(*s2))))
compareIdx := 0
for compareIdx < minLen {
if (*s1)[compareIdx] == (*s2)[compareIdx] {
compareIdx++
continue
}
break
}
return (*s1)[:compareIdx]
}
func main() {
s1 := "book"
s2 := "bool"
r1 := getCommonPrefix(&s1, &s2)
fmt.Printf("%s %s,common prefix:%s \n", s1, s2, r1) // bo
r2 := longestCommonPrefix(&[]string{"book", "bool", "bob", "bor", "abc"})
fmt.Printf("lcp: %s \n", r2) // 空字符串
r3 := longestCommonPrefix(&[]string{"book", "bool", "bob", "bor"})
fmt.Printf("lcp: %s \n", r3) // bo
}
时间复杂度 \(O(mn)\)，m为字符串的平均长度，n为数组长度；空间复杂度 \(O(1)\)。
上面的：
1
2
3
4
5
6
7
8
9
10
if len(*data) == 1 {
return (*data)[0]
}
lcp := (*data)[0]
for i := 1; i < len(*data); i++ {
lcp = getCommonPrefix(&lcp, &(*data)[i])
if lcp == "" {
return lcp
}
}
其实代码可以简化为：
1
2
3
4
5
6
7
lcp := (*data)[0]
for i := 0; i < len(*data); i++ {
lcp = getCommonPrefix(&lcp, &(*data)[i])
if lcp == "" {
return lcp
}
}
只是后者比前者多一次无谓的自己和自己比的检测，从效率角度来说不推荐。
纵向比较
我们最常想到的就是纵向比较，即纵向着一个一个比较字符，直到某一列（索引）上有字符串有不同字符为止。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func longestCommonPrefix(data *[]string) string {
if data == nil || len(*data) == 0 {
return ""
}
size := len(*data)
if size == 1 {
return (*data)[0]
}
tmpStr := (*data)[0]
tmpLength := len(tmpStr)
for i := 0; i < tmpLength; i++ {
char := tmpStr[i]
for j := 1; j < size; j++ {
if i == len((*data)[j]) || (*data)[j][i] != char {
// 某个字符串已经到头了，或者遍历到的字符在某个字符串上不匹配，可以退出了
return tmpStr[:i]
}
}
}
// 数组内字符串都一样
return tmpStr
}
时间复杂度仍然是 \(O(mn)\)，空间复杂度仍然为 \(O(1)\)。
分治
该问题除了满足 LCP(S1,S2...Sn)=LCP(LCP(LCP(S1,S2),S3),…Sn) 外，其实也满足 LCP(S1,S2…Sn)=LCP(LCP(S1,…Sk),LCP(Sk+1…Sn))，其中 1<k<n。
这正好适合用分治法和递归来解决问题，但是 k 怎么取呢？那么取个中间值吧。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
func longestCommonPrefix(data *[]string) string {
if data == nil || len(*data) == 0 {
return ""
}
size := len(*data)
if size == 1 {
return (*data)[0]
}
if size == 2 {
return getCommonPrefix(&(*data)[0], &(*data)[1])
}
mid := size >> 1
left := (*data)[:mid]
right := (*data)[mid:]
leftLCP := longestCommonPrefix(&left)
rightLCP := longestCommonPrefix(&right)
return getCommonPrefix(&leftLCP, &rightLCP)
}
func getCommonPrefix(s1, s2 *string) string {
minLen := int(math.Min(float64(len(*s1)), float64(len(*s2))))
compareIdx := 0
for compareIdx < minLen {
if (*s1)[compareIdx] == (*s2)[compareIdx] {
compareIdx++
continue
}
break
}
return (*s1)[:compareIdx]
}
时间复杂度仍然是 \(O(mn)\)，空间复杂度仍然为 \(O(mlogn)\)。
前缀比较
把第一个字符串当成最长公共前缀，查找这个最长公共前缀在其它字符串的索引，索引为0则是前缀，不为0则不是前缀，从右边缩短最长公共前缀，再次尝试，直到最终循环完毕。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func longestCommonPrefix(data *[]string) string {
if data == nil || len(*data) == 0 {
return ""
}
size := len(*data)
// 查找最小字符串长度
tmpStr := (*data)[0]
for i := 1; i < size; i++ {
for strings.Index((*data)[i], tmpStr) != 0 {
tmpStr = tmpStr[:len(tmpStr)-1]
}
}
return tmpStr
}
比较最大和最小字符串
先对字符串数组排序，得到最大和最小的字符串。对这两个字符串按字符遍历比较，直到找到字符不同或遍历结束。
注意：遍历的长度最大为最小字符串的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func longestCommonPrefix(data *[]string) string {
if data == nil || len(*data) == 0 {
return ""
}
// 对字符串数组排序
sort2.Strings(*data)
// 第一个是最小的
smallestStr := (*data)[0]
// 最后一个是最大的
biggestStr := (*data)[len(*data)-1]
idx := 0
for idx < len(smallestStr) && smallestStr[idx] == biggestStr[idx] {
idx++
}
return smallestStr[:idx]
}
二分查找
二分查找？？？
等等，先想想。
最长公共前缀的长度一定小于等于最短字符串的长度。设最短字符串长度为 minLength，每次查找时取中间值 mid，判断每个字符串的 [:mid] 是否都相同，若相同，则最长公共前缀的长度一定在 [mid,minLength] 区间内。然若有不同，则最长公共前缀的长度在 [0,minLength) 区间内。这样就缩小了查找范围。直到找到正好的最长公共前缀的长度，于是也就找到了最长公共前缀。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
func longestCommonPrefix(data *[]string) string {
if data == nil || len(*data) == 0 {
return ""
}
size := len(*data)
if size == 1 {
return (*data)[0]
}
// 查找最小字符串长度
tmpStr := (*data)[0]
minLength := len(tmpStr)
for i := 1; i < len(*data); i++ {
if len((*data)[i]) < minLength {
minLength = len((*data)[i])
}
}
leftIdx, rightIdx := 0, minLength
for leftIdx < rightIdx {
mid := (leftIdx + rightIdx + 1) >> 1 // 取平均值
if isCommonPrefix(data, mid) {
// 有公共前缀，往大搜索
leftIdx = mid
} else {
// 没有公共前缀，往小搜索
rightIdx = mid - 1
}
}
// 最终长度为 left
return tmpStr[:leftIdx]
}
// 字符串们是否在 length 长度范围内都有公共前缀
func isCommonPrefix(data *[]string, length int) bool {
tmp := (*data)[0][:length]
for i := 1; i < len(*data); i++ {
if (*data)[i][:length] != tmp {
// 发现有不同的前缀
return false
}
}
return true
}