leetcode 583. Delete Operation for Two Strings 问题转换+最长公共子串 + DP动态规划

Myth丶恋晨 2022-06-03 04:41 139阅读 0赞

Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string.

Example 1:  
Input: “sea”, “eat”  
Output: 2  
Explanation: You need one step to make “sea” to “ea” and another step to make “eat” to “ea”.  
Note:  
The length of given words won’t exceed 500.  
Characters in given words can only be lower-case letters.

本题题意很简单，就是求解两个字符串的公共子串，直接DP动态规划即可

很多题都是一个套路然后再换一个马甲，背题侠是没用的，要学会反思和学习，否者刷再多的题也没用

建议和[leetcode 712. Minimum ASCII Delete Sum for Two Strings 动态规划DP][leetcode 712. Minimum ASCII Delete Sum for Two Strings _DP] 一起学习

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    
    using namespace std;
    
    class Solution
    {
    public:
        int minDistance(string word1, string word2) 
        {
            vector<vector<int>> dp(word1.length()+1,vector<int>(word2.length()+1,0));
            int maxLen = 0;
            for (int i = 1; i <= word1.length(); i++)
            {
                for (int j = 1; j <= word2.length(); 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 word1.length()+word2.length()-2*dp[word1.length()][word2.length()];
        }
    };

[leetcode 712. Minimum ASCII Delete Sum for Two Strings _DP]: http://blog.csdn.net/jackzhang_123/article/details/78883782