最长公共前缀

字符串

说明

逐个缩短当前共同前缀；适合词典分组与自动补全。

分析

先以第一个单词作为候选前缀，再逐个与后续单词从头比较，保留相同的部分。一旦候选变空就可以提前结束。

图解推演

先用 flower 作候选，与 flow 比较后缩为 flow；再与 flight 比较，只有 fl 相同。候选只会缩短，绝不能因后续单词较长重新增长。空列表返回空串，列表中任何空串也会使共同前缀为空；rune 表示码点，仍不等于所有语言的可见字素。

查看图表代码

适用前提与边界

示例按 rune 比较，不会把中文字符截成无效的 UTF-8 字节片段。

示例输入与调用

fmt.Println(CommonPrefix([]string{"flower", "flow", "flight"}))

运行输出

fl

完整 Go 示例

package main

import "fmt"

func CommonPrefix(words []string) string {
	if len(words) == 0 {
		return ""
	}
	prefix := []rune(words[0])
	for _, word := range words[1:] {
		other := []rune(word)
		i := 0
		for i < len(prefix) && i < len(other) && prefix[i] == other[i] {
			i++
		}
		prefix = prefix[:i]
	}
	return string(prefix)
}

func main() {
	fmt.Println(CommonPrefix([]string{"flower", "flow", "flight"}))
}