专业网站建设哪家效果好,商标注册证,网站开发报价单.doc,涉县专业做网站583. 两个字符串的删除操作 1 、 dp[i][j] 表示 让以word1[i - 1]为结尾的字符串 和 以word2[i - 2]为结尾的字符串 相等需要删除的最少次数 1、dp[i][j] 的 递推需要考虑两种情况#xff1a; #xff08;1#xff09;word1[i - 1] word2[j - 1] 相当于不考虑word1[i]和… 583. 两个字符串的删除操作 1 、 dp[i][j] 表示 让以word1[i - 1]为结尾的字符串 和 以word2[i - 2]为结尾的字符串 相等需要删除的最少次数 1、dp[i][j] 的 递推需要考虑两种情况 1word1[i - 1] word2[j - 1] 相当于不考虑word1[i]和word2[j] 只考虑前面的 所以dp[i][j] dp[i - 1][j - 1] 2word1[i - 1] ! word2[j - 1] 如果不考虑word1[i - 1] 那么dp[i][j] dp[i - 1][j] 1; 如果不考虑word2[j - 1] 那么dp[i][j] dp[i][j - 1] 1 ; 如果都不考虑 那么dp[i][j] dp[i - 1][j - 1] 2 class Solution {
public:int minDistance(string word1, string word2) {int n word1.size();int m word2.size();vectorvectorint dp(n 1, vectorint(m 1));//dp[0][j] for(int i 0; i n; i) dp[i][0] i;for(int j 0; j m; j) dp[0][j] j;for(int i 1; i n; i) {for(int j 1; j m; 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] 1, dp[i][j - 1] 1);}}}return dp[n][m];}
}; 72. 编辑距离 1、dp[i][j]表示 以word1[i - 1]为结尾的字符串 - 以word2[j - 1]为结尾的字符串需要的最少操作次数 2、 word1[i - 1] word2[j - 1]相等 -不操作 dp dp[i -1][j - 1] 不相等 可以进行 增 删 换 1增 相当于 不考虑word2[j - 1] 操作数 1 (2) 删 相当于 不考虑word2[i -1] 操作数 1 (3) 换相当于 把word1[i - 1] 替换成word2[j - 1] 相当于 不考虑这俩 操作数 1 class Solution {
public:int minDistance(string word1, string word2) {int n word1.size();int m word2.size();vectorvectorint dp(n 1, vectorint(m 1));// dp[i][0]for(int i 0; i n; i) dp[i][0] i;for(int j 0; j m; j) dp[0][j] j; for(int i 1; i n; i) {for(int j 1; j m; 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] 1, min(dp[i][j - 1] 1, dp[i - 1][j - 1] 1));}}}return dp[n][m];}
};
