Problem statement

https://leetcode.com/problems/delete-operation-for-two-strings/

Solution

Almost the same as Problem 1143 Longest Common Subsequence. Let us define by dp(i, j) the length of the longgest common subsecuence. Then, what we need to return is m + n - 2*dp(m-1,n-1). We can use either dynamic programming for this:

  1. If i < 0 or j < 0, it means that one of the words is empty, so return 0.
  2. If word1[i] == word2[j], it means that we have common symbol, so return dp(i-1, j-1) + 1.
  3. Finally, if symbols are not equal, check two options: dp(i-1, j) and dp(i, j-1) and choose the best of them: maximum: because we want to find the longest commong subsequence.

#### Complexity Time and space complexity is O(mn).

Code

class Solution:
    def minDistance(self, word1, word2):
        @lru_cache(None)
        def dp(i,j):
            if i < 0 or j < 0: return 0
            if word1[i] == word2[j]: 
                return dp(i-1,j-1) + 1
            else:
                return max(dp(i-1,j), dp(i,j-1))

        m, n = len(word1), len(word2)
        return m + n - 2*dp(m-1, n-1)