编辑距离（Edit Distance）——从字符串相似度到动态规划经典模型
引言
在自然语言处理（NLP）、搜索引擎纠错、DNA序列比对、拼写检查系统等领域，经常需要衡量两个字符串之间的相似程度。
例如：
kitten sitting显然两个单词非常接近，但究竟有多接近？
如何用数学方法描述这种“接近程度”？
为了解决这一问题，俄罗斯科学家 Vladimir Levenshtein 于 1965 年提出了著名的Levenshtein Distance（编辑距离）。
编辑距离定义为：
将一个字符串转换为另一个字符串所需要执行的最少编辑操作次数。
允许的操作包括：
插入（Insert）
删除（Delete）
替换（Replace）
问题描述
给定两个字符串：
word1 word2求将word1转换为word2所需的最少操作次数。
例如：
horse → ros转换过程：
horse ↓ replace(h,r) rorse ↓ delete(r) rose ↓ delete(e) ros答案：
3编辑距离的本质
假设：
word1 = horse word2 = ros我们关注的是：
horse前i个字符 与 ros前j个字符之间的最优转换方案。
因此可以发现：
一个大问题可以分解为若干个更小的子问题。
这正是动态规划的典型特征。
动态规划状态定义
设：
dp[i][j]表示：
word1前i个字符 转换成 word2前j个字符 所需的最少操作次数例如：
dp[3][2]表示：
"hor" → "ro"的最小编辑距离。
状态转移推导
这是整道题最核心的部分。
情况一：字符相同
假设：
word1[i-1] == word2[j-1]例如：
abc abc最后一个字符已经匹配：
c == c无需额外操作。
因此：
dp[i][j] = dp[i-1][j-1]情况二：字符不同
假设：
word1[i-1] != word2[j-1]例如：
horse ros最后一个字符不同。
此时有三种选择。
1. 删除
删除 word1 的最后一个字符：
horse ↓ hors问题变成：
dp[i-1][j]再加一次删除操作：
dp[i-1][j] + 12. 插入
向 word1 末尾插入一个字符：
hors ↓ horse对应：
dp[i][j-1]再执行一次插入：
dp[i][j-1] + 13. 替换
直接修改最后一个字符：
horse ↓ rorse对应：
dp[i-1][j-1]加一次替换：
dp[i-1][j-1] + 1综合状态转移方程
因此得到：
dp[i][j]=\min\left(dp[i-1][j]+1,\ dp[i][j-1]+1,\ dp[i-1][j-1]+cost\right)
其中：
cost = 0 (字符相同) 1 (字符不同)或者写成：
if(word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1]; else dp[i][j] = min({ dp[i-1][j], // 删除 dp[i][j-1], // 插入 dp[i-1][j-1] // 替换 }) + 1;初始化分析
动态规划中最容易忽略的部分就是边界条件。
第一列
dp[i][0]表示：
word1前i个字符 → 空串唯一办法：
全部删除因此：
dp[i][0] = i;第一行
dp[0][j]表示：
空串 → word2前j个字符只能不断插入：
dp[0][j] = j;DP表格演示
以：
word1 = horse word2 = ros为例：
| "" | r | o | s | |
|---|---|---|---|---|
| "" | 0 | 1 | 2 | 3 |
| h | 1 | 1 | 2 | 3 |
| o | 2 | 2 | 1 | 2 |
| r | 3 | 2 | 2 | 2 |
| s | 4 | 3 | 3 | 2 |
| e | 5 | 4 | 4 | 3 |
最终：
dp[5][3]即：
3代码实现
class Solution { public: int minDistance(string word1, string word2) { int m = word1.size(); int n = word2.size(); vector<vector<int>> dp( m + 1, vector<int>(n + 1, 0) ); // 初始化 for(int i = 0; i <= m; i++) dp[i][0] = i; for(int j = 0; j <= n; j++) dp[0][j] = j; // 状态转移 for(int i = 1; i <= m; i++) { for(int j = 1; j <= n; j++) { if(word1[i-1] == word2[j-1]) { dp[i][j] = dp[i-1][j-1]; } else { dp[i][j] = min({ dp[i-1][j], // 删除 dp[i][j-1], // 插入 dp[i-1][j-1] // 替换 }) + 1; } } } return dp[m][n]; } };空间优化
观察状态转移：
dp[i][j]仅依赖于：
dp[i-1][j] dp[i][j-1] dp[i-1][j-1]即：
当前行
上一行
因此可以压缩成：
O(n)空间复杂度。
优化后：
时间复杂度：O(mn) 空间复杂度：O(n)编辑距离的现实应用
编辑距离远不止是一道算法题。
它广泛应用于工业系统。
搜索引擎纠错
用户输入：
googel系统自动纠正：
google因为：
EditDistance(googel, google)=2拼写检查器
例如：
Microsoft Word
VSCode
IntelliJ IDEA
都会计算候选词的编辑距离。
DNA序列比对
生物信息学中：
ACTGCA ACTACA可以通过编辑距离衡量基因序列相似度。
OCR文字识别
识别结果：
ChatGP7真实结果：
ChatGPT编辑距离：
1系统可以自动修正。
动态规划思想总结
编辑距离是动态规划中的经典代表问题，其核心思想可以概括为：
将字符串问题转化为二维状态空间。
定义
dp[i][j]表示两个前缀字符串的最优解。根据最后一个字符是否相同进行分类讨论。
将复杂转换过程归结为：
插入
删除
替换
最终建立最优子结构关系。
从算法体系角度看，编辑距离与：
最长公共子序列（LCS）
最长公共子串
不同的子序列
正则表达式匹配
共同构成了字符串动态规划（String DP）的重要基础，其思想在自然语言处理、生物信息学以及搜索推荐系统中均具有广泛应用价值。