# LC 583. Delete Operation for Two Strings

### [Problem link](https://leetcode.com/problems/delete-operation-for-two-strings/)

###### tags: `leedcode` `python` `c++` `medium` `DP` `LCS`

Given two strings <code>word1</code> and <code>word2</code>, return the minimum number of **steps** required to make <code>word1</code> and <code>word2</code> 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

**Constraints:**

- <code>1 <= word1.length, word2.length <= 500</code>
- <code>word1</code> and <code>word2</code> consist of only lowercase English letters.

## Solution 1 - DP

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        # dp[i][j] = word1[:i] 到 word2[:j] 最少需要刪除幾個字母

        for i in range(1, m + 1):
            dp[i][0] = i
        for i in range(1, n + 1):
            dp[0][i] = i

        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]
                else:
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1

        return dp[-1][-1]

## Solution 2 - DP

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size() + 1, vector<int> (word2.size() + 1, 0));
        for (int i = 0; i < word1.size(); i++) {
            for (int j = 0; j < word2.size(); j++) {
                if (word1[i] == word2[j]) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                } else {
                    dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
                }
            }
        }
        int maxSubArrLen = dp.back().back();
        return word1.size() + word2.size() - maxSubArrLen * 2;
    }
};

>### Complexity
>m = len(word1)
>n = len(word2)
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(mn) | O(mn) |
>| Solution 1 | O(mn) | O(mn) |

## Note
sol2:
跟[LC 1143. Longest Common Subsequence](https://hackmd.io/@Alone0506/BJDk6iZFh)想法一樣, 要刪掉的字母就是除了最長子字串外的所有字母