当前位置：首页 > news >正文

代码随想录第五十九天 | 115.不同的子序列，583. 两个字符串的删除操作， 72. 编辑距离

news 来源：原创 2024/9/18 0:57:50

115.不同的子序列

看完想法：这个题目只涉及删减，具体是 s 字符串的删减，t 不需要动。当s[ i ] == t[j]时，有两种情况，可以用s[i]也可以不用，而s[i] !=t[j]时只有一种情况，需要删除s[i]进一步比较。在初始化时，不要臆想，要根据dp [i][j]定义初始化。dp[i][0] 表示：以i-1为结尾的s可以随便删除元素，出现空字符串的个数，肯定为1；dp[0][j]一定都是0，s如论如何也变成不了t；dp[0][0]应该是1，空字符串s，可以删除0个元素，变成空字符串t。

int numDistinct(string s, string t) {//uint64_t代表unsigned long int，有8个字节，直接用int会溢出vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1));//dp数组初始化for (int i = 0; i < s.size(); i++) dp[i][0] = 1;for (int j = 1; j < t.size(); j++) dp[0][j] = 0;//dp递推for (int i = 1; i <= s.size(); i++) {for (int j = 1; j <= t.size(); j++) {if (s[i - 1] == t[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];} else {dp[i][j] = dp[i - 1][j];}}}return dp[s.size()][t.size()];}

583. 两个字符串的删除操作

看完想法：这里删除操作需要取最小值，如果s[i] == t[j]，不用作操作，继承上次dp;如果不太相同就需要删除，包含3种情况，删除s / 删除t / 两个都删。

int minDistance(string word1, string word2) {//dp初始化vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));//此处以要注意，下标为i-1的字符串变成0，需要i次操作for(int i = 0; i<= word1.size();i++) dp[i][0] = i;for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;//dp迭代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];} else {dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);}}}return dp[word1.size()][word2.size()];

72. 编辑距离

看完想法：在进行dp迭代时，删除元素和添加元素可以公用一个式子，因为删除word1和添加word2时等价的，操作数都一样；替换元素也只有一次操作数dp[i][j] = dp[i - 1][j - 1] + 1。综上，dp[i][j]取3个式子中的最小值。

int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));//初始化，和之前的题目大同小异，结尾为i-1的word1如何变成0for(int i = 0; i<= word1.size(); i++) dp[i][0] = i;for(int i = 0; i<= word2.size(); i++) dp[0][i] = i;//dp迭代，注意0已经初始化，要从i, j =1开始for(int i =1; i<=word1.size() ;i++){for(int j = 1; j<=word2.size(); j++){//这需要分当前遍历的word1和word2元素相等/不相等//相等不做操作，不相等要增删减if(word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1];else{//min操作（中间还需要一个{}），针对3个及以上的元素dp[i][j] = min({dp[i-1][j] , dp[i][j-1] , dp[i-1][j-1]}) + 1;}}}return dp[word1.size()][word2.size()];