在自然语言处理、拼写纠错、模糊搜索等场景中，我们经常需要衡量两个字符串之间的相似度。编辑距离（Edit Distance） 就是一个经典的衡量方式，它描述了将一个字符串转换为另一个字符串所需的最少操作次数。
一、问题定义：什么是编辑距离？
编辑距离，也称为 Levenshtein Distance，指的是将字符串 A 转换成字符串 B 所需的最少操作次数。操作允许：
- • 插入一个字符（Insert）
- • 删除一个字符（Delete）
- • 替换一个字符（Replace）
示例：
A = "kitten"
B = "sitting"编辑距离 = 3
解释：
kitten → sitten（k → s） → sittin（e → i）→ sitting（插入 g）二、应用场景
编辑距离广泛应用于：
- • 搜索引擎模糊匹配（例如：“gooogle” 应该匹配 “google”）
- • 拼写检查和自动纠正
- • 语音识别、OCR纠错
- • DNA序列比对
三、解决思路：动态规划（DP）
1. 状态定义
设 dp[i][j] 表示将字符串 A 的前 i 个字符转换成字符串 B 的前 j 个字符所需的最小操作数。
2. 状态转移方程
我们可以从三个方向转移过来：
- • 插入：
dp[i][j-1] + 1（B 多了个字符） - • 删除：
dp[i-1][j] + 1（A 多了个字符） - • 替换或匹配：
dp[i-1][j-1] + cost- • 如果
A[i-1] == B[j-1]，cost = 0 - • 否则
cost = 1
- • 如果
最终状态转移为：
dp[i][j] = min(
dp[i-1][j] + 1, // 删除
dp[i][j-1] + 1, // 插入
dp[i-1][j-1] + cost 
