72. 编辑距离
3 min
题目
解法：动态规划
思路
核心思想是动态规划，定义 dp[i][j] 表示 word1 前 i 个字符转换为 word2 前 j 个字符的最少操作数，通过状态转移方程递推求解。
正确性基于最优子结构和无后效性。对于任意位置 (i,j)，若字符相等则无需操作，直接继承 dp[i-1][j-1]；若不相等，则三种操作中取最小值：删除（dp[i-1][j]+1）、插入（dp[i][j-1]+1）、替换（dp[i-1][j-1]+1）。这种自底向上的方式确保每个子问题最优，从而保证全局最优。
- Step 1: 初始化 DP 表大小为 (m+1) × (n+1)，dp[i][0] = i（全删除），dp[0][j] = j（全插入）
- Step 2: 遍历 i 从 1 到 m，j 从 1 到 n
- Step 3: 若 word1[i-1] == word2[j-1]，则 dp[i][j] = dp[i-1][j-1]
- Step 4: 否则 dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
- Step 5: 返回 dp[m][n]
复杂度
- 时间复杂度:
- 空间复杂度:
代码
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 = 1; i <= m; i++){
dp[i][0] = i;
}
for(int i = 1; i <= n; i++){
dp[0][i] = i;
}
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( min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]) + 1;
}
}
}
return dp[m][n];
}
};