介绍 Levenshtein 编辑距离算法原理及 Go 语言实现。涵盖动态规划状态转移方程、Unicode 字符处理（rune）、标准二维 DP 与空间优化版本代码。包含时间复杂度 O(m*n) 分析及常见问题解答，适用于拼写纠错、模糊匹配等场景。
在字符串处理、自然语言处理（NLP）、搜索引擎、拼写纠错、模糊匹配、DNA 序列分析等领域，编辑距离（Edit Distance） 是一个极其重要的算法。其中最经典、最广泛使用的就是 Levenshtein 距离算法。
Levenshtein 距离由俄罗斯数学家 Vladimir Levenshtein 在 1965 年提出，用于衡量两个字符串之间的相似程度。
编辑距离表示将字符串 A 转换为字符串 B 所需的最少编辑操作次数。
允许的三种基本操作：
例 1：kitten → sitting
操作过程：
编辑距离 = 3
例 2：flaw → lawn
操作：
编辑距离 = 2
实现函数：
func Levenshtein(a, b string) int
功能：
示例 1： 输入："kitten", "sitting" 输出：3
示例 2： 输入："flaw", "lawn" 输出：2
示例 3（Unicode）： 输入："你好", "您好" 输出：1
Levenshtein 算法本质是二维动态规划问题。
定义： dp[i][j] = a 的前 i 个字符 与 b 的前 j 个字符 的最小编辑距离
状态转移方程：
如果 a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1] 否则: dp[i][j] = min( dp[i-1][j] + 1, // 删除 dp[i][j-1] + 1, // 插入 dp[i-1][j-1] + 1 // 替换 )
设 m = len(a), n = len(b)。
时间复杂度：O(m * n) 空间复杂度：O(m * n)，可优化为 O(min(m, n))。
Go 字符串是 UTF-8 编码。必须转换为 []rune，否则中文会出错。
转为 rune 数组 ra := []rune(a) rb := []rune(b)
创建二维 DP 数组 dp := make([][]int, m+1)
初始化边界 dp[i][0] = i dp[0][j] = j
填表 根据状态转移公式计算。
返回结果 dp[m][n]
// ===================================== // file: distance/levenshtein.go // ===================================== package distance
// DistanceCalculator 编辑距离计算器
type DistanceCalculator struct{}
// NewDistanceCalculator 构造函数
func NewDistanceCalculator() *DistanceCalculator {
return &DistanceCalculator{}
}
// -------------------------------------------------- // 标准二维动态规划版本（推荐教学版） // --------------------------------------------------
func (d *DistanceCalculator) Levenshtein(a, b string) int {
ra := []rune(a)
rb := []rune(b)
m := len(ra)
n := len(rb)
// 创建二维 DP 数组
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
// 初始化边界
for i := 0; i <= m; i++ {
dp[i][0] = i
}
for j := 0; j <= n; j++ {
dp[0][j] = j
}
// 填充 DP 表
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if ra[i-1] == rb[j-1] {
dp[i][j] = dp[i-1][j-1]
} else {
dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1)
}
}
}
return dp[m][n]
}
// -------------------------------------------------- // 空间优化版本（滚动数组） // 空间复杂度 O(min(m,n)) // --------------------------------------------------
func (d *DistanceCalculator) LevenshteinOptimized(a, b string) int {
ra := []rune(a)
rb := []rune(b)
if len(ra) < len(rb) {
ra, rb = rb, ra
}
m := len(ra)
n := len(rb)
prev := make([]int, n+1)
curr := make([]int, n+1)
for j := 0; j <= n; j++ {
prev[j] = j
}
for i := 1; i <= m; i++ {
curr[0] = i
for j := 1; j <= n; j++ {
if ra[i-1] == rb[j-1] {
curr[j] = prev[j-1]
} else {
curr[j] = min(prev[j]+1, curr[j-1]+1, prev[j-1]+1)
}
}
prev, curr = curr, prev
}
return prev[n]
}
// min 辅助函数
func min(a, b, c int) int {
if a < b {
if a < c {
return a
}
return c
}
if b < c {
return b
}
return c
}
// ===================================== // file: main.go // =====================================
package main
import (
"fmt"
"distance/distance"
)
func main() {
calculator := distance.NewDistanceCalculator()
fmt.Println("标准版本:")
fmt.Println(calculator.Levenshtein("kitten", "sitting"))
fmt.Println("优化版本:")
fmt.Println(calculator.LevenshteinOptimized("flaw", "lawn"))
fmt.Println("Unicode 测试:")
fmt.Println(calculator.Levenshtein("你好", "您好"))
}
本项目实现：
时间复杂度：O(m * n) 空间复杂度：
因为 Go 字符串是 UTF-8。中文字符占多个字节。如果用 byte 会出错。
可以。将 +1 替换为 +cost 即可实现加权编辑距离。
在一般情况下无法突破 O(m*n)。但可以提前剪枝或使用带阈值的算法。
增加操作：相邻字符交换。
结合字典、Trie 树、编辑距离阈值。
用于搜索引擎、商品匹配、用户名检测。
用于 DNA 序列匹配、蛋白质序列分析。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online