# 583. Delete Operation for Two Strings

{% embed url="<https://leetcode.com/problems/delete-operation-for-two-strings/>" %}

求 `Longest Common String`，跟 common 有关的很多都是DP题，这题虽然是二维DP，状态转换方程还挺简单的。

`bottom-up`和`top-down`都能写，但`top-down`的结构在 Python 里实现起来有点tricky，而且也慢。`bottom-up`可以直接拿数组记录，简单一些。

{% tabs %}
{% tab title="Top-down" %}

```python
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = collections.defaultdict(lambda :collections.defaultdict(int))
        return len(word1) + len(word2) - 2 * self.LCS(word1, word2, m, n, dp)
        
    # longest common string
    def LCS(self, a, b, m, n, dp):
        if not m or not n:
            return 0
        if dp[m][n]:
            return dp[m][n]
        if a[m-1] == b[n-1]:
            dp[m][n] = 1 + self.LCS(a, b, m-1, n-1, dp)
        else:
            dp[m][n] = max([self.LCS(a, b, m-1, n, dp), self.LCS(a, b, m, n-1, dp)])
        return dp[m][n]
```

{% endtab %}

{% tab title="Bottom-up" %}

```python
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        if not m and not n: return 0
        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):
                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]
```

{% endtab %}
{% endtabs %}
