我要评论72. 编辑距离（困难）
-
思路
- 状态定义：「
dp[i][j]表示第一个字符串到 i ，第二个字符串到 j，要想使得 word1 == word2 ，最少的修改次数」。 - 状态转移方程：
- 当第 i 位和第 j 位对应的字符相同时，
dp[i][j] = dp[i-1][j-1]； - 当第 i 位和第 j 位对应的字符不同时，有三种修改方式：（1）替换第 i 位：
dp[i][j] = dp[i-1][j-1] + 1；（2）删除第 i 位：dp[i][j] = dp[i-1][j] + 1；（3）插入第 i 位：dp[i][j] = dp[i][j-1] + 1。要使得修改次数最小，就是在三种方案中选择最小的 dp[i][j] ，即dp[i][j] = min(min(dp[i-1][j-1],dp[i-1][j]), dp[i][j-1]) + 1;
- 当第 i 位和第 j 位对应的字符相同时，
- 初始化： 需要考虑到 i=0 和 j=0 的情况，当i=0 时，那么只能选择插入，才能等于字符串 word2， 此时的操作次数为 word2 的长度（j），所以
dp[i][j] = j；当 j=0 时，只能选择删除，此时的操作次数为 word1 的长度（即 i），所以dp[i][j] = i；
- 状态定义：「
-
代码
class solution { public: int mindistance(string word1, string word2) { int n1 = word1.size(), n2 = word2.size(); vector<vector<int>> dp(n1+1, vector<int>(n2+1, 0)); for(int i=0; i<=n1; ++i){ for(int j=0; j<=n2; ++j){ // 这题第一行和第一列需要额外初始化 if(i == 0){ // 第一个字符串为空，想要转变成第二个字符串 // 需要有j(第二个字符串当前的长度)个插入操作 dp[i][j] = j; } else if(j == 0){ dp[i][j] = i; } else{ 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-1],dp[i-1][j]), dp[i][j-1]) + 1; } } } } return dp[n1][n2]; } }; -
收获
- 看到困难题就放弃了，不过思路蛮简单的，状态定义和 1143 （求两个字符串的最长公共子串）类似。因此对于比较两个字符串的题目，可以总结为： 「如果是比较两个字符串，那么状态就定义为 ：
dp[i][j] 表示为 第一个字符串到 i ，第二个字符串到 j 为止的属性」。 - 此外，不是所有 dp数组的初始化都为 0 ，像求得最小值的时候（如 322） ，就得定义一个较大的值，才便于比较；而像这题，需要具体考虑初始值。
- 看到困难题就放弃了，不过思路蛮简单的，状态定义和 1143 （求两个字符串的最长公共子串）类似。因此对于比较两个字符串的题目，可以总结为： 「如果是比较两个字符串，那么状态就定义为 ：
发表评论