Leetcode 583. Delete Operation for Two Strings (python+cpp)

题目

解法：动态规划

这道题乍一看可能会觉得跟71 edit distance一样，但实际上是不一样的，这边只有delete操作，但对于两个word都可以操作。实质上和300 longest increasing subsequency是一模一样的，求出longest increasing subsequency的答案为L，word1长度为m，word2的长度为n，本题所求答案为m+n-2L.
python代码：

class Solution:def minDistance(self, word1: str, word2: str) -> int:m = len(word1)n = len(word2)dp = [[0]*(n+1) for _ in range(m+1)]for i in range(1,m+1):for j in range(1,n+1):if word1[i-1]==word2[j-1]:dp[i][j] = dp[i-1][j-1]+1else:dp[i][j] = max(dp[i-1][j],dp[i][j-1])return m+n-2*dp[m][n]

C++代码如下：

class Solution {
    
public:int minDistance(string word1, string word2) {
    int m = word1.size(), n = word2.size();vector<vector<int>> dp(m+1,vector<int>(n+1,0));for (int i=1;i<=m;i++){
    for (int j=1;j<=n;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 m+n-2*dp[m][n];}
};