编辑距离-二维动态规划

编辑距离

Solution

枚举每一种操作即可

#include<iostream>
#include<string>
#include<vector>
using namespace std;const int inf = 1e9;
//递归做法
//f(i,j)表示从s1的i开始到s2的j开始，（选择到了s1的第i个字符，s2的第j个字符）所需要的最少操作数
//对于每一个状态，枚举各种操作，取最小值即可
//写的时候出现的核心问题就是base case的错误，当某一个字符串到达结尾的时候，不应该直接返回inf，应该考虑插入和删除
int f1(string s1, string s2, int i, int j) {int n1 = s1.length();int n2 = s2.length();if (i == n1 && j == n2)return 0;//错误就出现在这里/*if (i >= n1 || j >= n2) return inf;*///正确的base caseif (i == n1 && j < n2)//后面全部插入return n2 - j;if (j == n2 && i < n1)//后面全部删除return n1 - i;int ans1 = inf, ans2 = inf, ans3 = inf, ans4 = inf;if (s1[i] == s2[j]) ans1 = f1(s1, s2, i + 1, j + 1);//对应直接pass的情况else {ans2 = f1(s1, s2, i + 1, j + 1) + 1;//对应替换的情况ans3 = f1(s1, s2, i + 1, j) + 1;//对应删除的情况ans4 = f1(s1, s2, i, j + 1) + 1;//对应插入一个字符的情况}return min(ans1, min(ans2, min(ans3, ans4)));
}//dp做法
int f2(string s1, string s2) {int n1 = s1.length();int n2 = s2.length();vector<vector<int>>dp(n1 + 1, vector<int>(n2 + 1, 0));for (int i = n1; i >= 0; --i) {for (int j = n2; j >= 0; --j) {int ans1 = inf, ans2 = inf, ans3 = inf, ans4 = inf;if (i == n1 && j == n2) {dp[i][j] = 0;continue;}if (i == n1 && j < n2) {dp[i][j] = n2 - j;continue;}if (j == n2 && i < n1) {dp[i][j] = n1 - i;continue;}if (s1[i] == s2[j])ans1 = dp[i + 1][j + 1];ans2 = dp[i + 1][j + 1] + 1;ans3 = dp[i + 1][j] + 1;ans4 = dp[i][j + 1] + 1;dp[i][j] = min(ans1, min(ans2, min(ans3, ans4)));}}return dp[0][0];
}//dp+空间压缩
int f3(string s1, string s2) {int n1 = s1.length();int n2 = s2.length();vector<int>dp(n2 + 1, 0);int rightdown = 0, back;for (int i = n1; i >= 0; --i) {for (int j = n2; j >= 0; --j) {int ans1 = inf, ans2 = inf, ans3 = inf, ans4 = inf;back = dp[j];if (i == n1 && j == n2) {dp[j] = 0;}else if (i == n1 && j < n2) {dp[j] = n2 - j;}else if (j == n2 && i < n1) {dp[j] = n1 - i;}else {if (s1[i] == s2[j])ans1 = rightdown;ans2 = dp[j + 1] + 1;ans3 = rightdown + 1;ans4 = dp[j] + 1;dp[j] = min(ans1, min(ans2, min(ans3, ans4)));}rightdown = back;}}return dp[0];
}
int minDistance1(string word1, string word2) {return f1(word1, word2, 0, 0);
}int minDistance2(string word1, string word2) {return f2(word1, word2);
}int minDistance(string word1, string word2) {return f3(word1, word2);
}
int main() {return 0;
}