LeetCode 583两个字符串的删除操作 72编辑距离

LeetCode 583两个字符串的删除操作 72编辑距离 | 代码随想录25期训练营day56

本文主要是介绍LeetCode 583两个字符串的删除操作 72编辑距离 | 代码随想录25期训练营day56，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

动态规划算法13

LeetCode 583 两个字符串的删除操作 2023.12.19

题目链接
代码随想录讲解[链接]

int minDistance(string word1, string word2) {//思路1，求除了最长公共序列外，两个字符串需删除的字符数//以下为求最长公共序列长度的动态规划方法/*vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1, 0));for (int i = 1; i <= word1.size(); i++){for(int j = 1; j <= word2.size(); j++){if(word1[i-1] == word2[j-1])dp[i][j] = dp[i-1][j-1] + 1;elsedp[i][j] = max(dp[i-1][j], dp[i][j-1]);}}//最后返回word1、word2相对最长公共序列需要操作的次数和return (word1.size()-dp[word1.size()][word2.size()])+(word2.size()-dp[word1.size()][word2.size()]);*///思路2，单纯计算两个字符串需要的最小操作次数//1确定二维dp数组，dp[i][j]表示以word1[0, i-1]字符串与word2[0, j-1]字符串相同的最小操作次数vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1, 0));//3初始化dp数组，由于递推公式中dp[i][j]可由dp[i-1][j-1]、dp[i][j-1]、dp[i-1][j]得到//那么初始化首行与首列，dp[0][i]含义为空字符串与以word2[0, i-1]字符串相同的最小操作次数，那么为ifor (int i = 0; i <= word1.size(); i++)dp[i][0] = i;for (int i = 0; i <= word2.size(); i++)dp[0][i] = i;//2确定递推公式 4确定遍历顺序//顺序遍历for (int i = 1; i <= word1.size(); i++){for(int j = 1; j <= word2.size(); j++){//word1[i-1] == word2[j-1]时，不用操作，dp[i][j]=dp[i-1][j-1]if(word1[i-1] == word2[j-1])dp[i][j] = dp[i-1][j-1];//不相等时，需要操作，那么取一个最小操作次数//dp[i][j-1]需对word2删除一个，dp[i-1][j]需对word1删除一个，dp[i-1][j-1]需对word1、word2分别删除一个elsedp[i][j] = min(min(dp[i][j-1] + 1, dp[i-1][j] + 1), dp[i-1][j-1] + 2);}}//最后返回word1与word2达到相同的最小操作次数return dp[word1.size()][word2.size()];
}

LeetCode 72 编辑距离 2023.12.19

题目链接
代码随想录讲解[链接]

int minDistance(string word1, string word2) {//1确定二维dp数组，dp[i][j]表示以word1[0, i-1]字符串与word2[0, j-1]字符串相同的最小操作次数vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1, 0));//3初始化dp数组，由于递推公式中dp[i][j]可由dp[i-1][j-1]、dp[i][j-1]、dp[i-1][j]得到//那么初始化首行与首列，dp[0][i]含义为空字符串与以word2[0, i-1]字符串相同的最小操作次数，那么为ifor (int i = 0; i <= word1.size(); i++)dp[i][0] = i;for (int i = 0; i <= word2.size(); i++)dp[0][i] = i;//2确定递推公式 4确定遍历顺序//顺序遍历for (int i = 1; i <= word1.size(); i++){for(int j = 1; j <= word2.size(); j++){//word1[i-1] == word2[j-1]时，不用操作，dp[i][j]=dp[i-1][j-1]if(word1[i-1] == word2[j-1])dp[i][j] = dp[i-1][j-1];//不相等时，需要操作，那么取一个最小操作次数//dp[i][j-1]需对word2删除(或增加)一个，dp[i-1][j]需对word1删除(或增加)一个，dp[i-1][j-1]需对word1或word2替换一个elsedp[i][j] = min(min(dp[i-1][j]+1, dp[i][j-1]+1), dp[i-1][j-1]+1);}}//最后返回word1与word2达到相同的最小操作次数return dp[word1.size()][word2.size()];
}