编辑距离
进阶编辑距离用 DP 枚举插入、删除、替换三种操作的最优路径。
// 算法讲解
编辑距离
与排序后的序列求编辑距离，观察 DP 表填充。
待机
速度 中
待机 ⌨1int editDistance(string s1, string s2) {
2 int m = s1.size(), n = s2.size();
3 vector<vector<int>> dp(m + 1, vector<int>(n + 1));
4 for (int i = 0; i <= m; i++) dp[i][0] = i;
5 for (int j = 0; j <= n; j++) dp[0][j] = j;
6 for (int i = 1; i <= m; i++)
7 for (int j = 1; j <= n; j++) {
8 int cost = s1[i-1] != s2[j-1];
9 dp[i][j] = min({dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + cost});
10 }
11 return dp[m][n];
12}
复杂度分析
时间 O(mn)
空间 O(mn)
最优 O(mn)
最坏 O(mn)
算法讲解
编辑距离（Levenshtein Distance）允许三种操作：插入、删除、替换，求从 s1 变到 s2 的最少操作数。
dp[i][j] 表示 s1 前 i 个字符变到 s2 前 j 个字符的最小操作数。
转移：dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1] + (s1[i-1]!=s2[j-1]))。
它在拼写检查、DNA 比对和自然语言处理中有广泛应用。