河北网络公司网站建设,做电商的进货网站,wordpress post 请求,昆明小程序公司583. 两个字符串的删除操作方法#xff1a;dp状态表示#xff1a;以i-1和j-1为结尾的字符串world1和world2#xff0c;抵达相同的字符串所需的最少操作数属性#xff1a;最小值状态计算#xff1a;world1[i-1]和world2[j-1]相同dp[i][j] dp[i-1][j-1];world1[i-1]和world…583. 两个字符串的删除操作方法dp状态表示以i-1和j-1为结尾的字符串world1和world2抵达相同的字符串所需的最少操作数属性最小值状态计算world1[i-1]和world2[j-1]相同dp[i][j] dp[i-1][j-1];world1[i-1]和world2[j-1]不相同删去world1:dp[i-1][j] 1,就变为以i-2和j-1为结尾的字符串world1和world2抵达相同的字符串所需的最少操作数同理删除world2:dp[i][j-1] 1;同时删除world1和world2:dp[i-1][j-1] 2;细心的话可以发现dp[i-1][j] 1 dp[i-1][j-1] dp[i][j-1] 1所以递推公式dp[i][j] min(dp[i-1][j] 1, dp[i][j-1] 1)class Solution {
public:int minDistance(string word1, string word2) {int n word1.size(), m word2.size();vectorvectorint dp(n 1, vectorint (m 1, 0));for (int i 0; i n; i) dp[i][0] i;for (int i 0; i m; i) dp[0][i] i;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];}
};$时间复杂度O(n*m)空间复杂度O(n*m);方法2dp状态表示以i-1和j-1为结尾的字符串world1和world2最大的相同子序列的集合为dp[i][j]class Solution {
public:int minDistance(string word1, string word2) {int n word1.size(), m word2.size();vectorvectorint dp(n 1, vectorint (m 1, 0));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] 1;else dp[i][j] max(dp[i-1][j], dp[i][j-1]);}return n m - dp[n][m] * 2;}
};$时间复杂度O(n*m)空间复杂度O(n*m);72. 编辑距离方法dp简单说一下增加和删除的效果是一样的所以就统一删除了替换就是在dp[i-1][j-1]的基础上加一个操作其他的都差不多class Solution {
public:int minDistance(string word1, string word2) {int n word1.size(), m word2.size();vectorvectorint dp(n 1, vectorint (m 1, 0));for (int i 0; i n; i) dp[i][0] i;for (int i 0; i m; i) dp[0][i] i;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], dp[i][j-1], dp[i-1][j-1]}) 1;}return dp[n][m];}
};$时间复杂度O(n*m)空间复杂度O(n*m);
