###### tags: `Leetcode` `medium` `dynamic programming` `python` `c++`

# 583. Delete Operation for Two Strings

## [題目連結:] https://leetcode.com/problems/delete-operation-for-two-strings/description/

## 題目:
Given two strings ```word1``` and ```word2```, return the minimum number of **steps** required to make ```word1``` and ```word2``` the same.

In one **step**, you can delete exactly one character in either string.

**Example 1:**

Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

**Example 2:**

Input: word1 = "leetcode", word2 = "etco"
Output: 4

## 解題想法:
* 此題目為刪除多少字使word1、word2為same，且不用是連續的
* ex:
* w1:bcbda
* w2:caba
* same=cba
* 即為**最長子序列LCS**
* 使用DP:
* dp[i][j]:**W1中前i個字與W2中前j個字，最長的共同子串長度**
* 若w1[x]==w2[y]:
* dp[x][y]=dp[x-1][y-1]+1
* 若w1[x]!=w2[y]:
* dp[x][y]=max(dp[x-1][y],dp[x][y-1])

## Python:

class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        #最長子序列LCS
        #dp[i][j]:W1中前i個字與W2中前j個字 最長的共同子串長度
        m=len(word1)
        n=len(word2)
        dp=[[0 for _ in range(n+1)] for _ in range(m+1)]
        for i in range(1,m+1):
            for j in range(1,n+1):
                #行列各多一維 所以真正的i j 為i-1 j-1
                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])
        same=dp[-1][-1]
        return m+n-2*same
    
result=Solution()
word1="bcbda"
word2="caba"
ans=result.minDistance(word1,word2)
print(ans)

## 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+1; i++){
            for (int j=1; j<n+1; 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]);
            }
        }
        int same=dp[m][n];
        return m+n-2*same;
    }
};