# 583 Delete Operation for Two Strings

## 583. [Delete Operation for Two Strings](https://leetcode.com/problems/delete-operation-for-two-strings/description/)

## 1. Question

Given two wordsword1andword2, find the minimum number of steps required to makeword1andword2the 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:**

1. The length of given words won't exceed 500.
2. Characters in given words can only be lower-case letters.

## 2. Implementation

**(1) DP**

思路: 找两个string之间的LCS，需要删除的操作就等于两个string的长度 - 2 \* LCS

```java
class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();

        int[][] dp = new int[m + 1][n + 1];

        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 0;
                }
                else if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return m + n - 2 * dp[m][n];
    }
}
```

## 3. Time & Space Complexity

**DP:** 时间复杂度: O(mn), 空间复杂度O(mn)