Problem Statement in English

You’re given two strings word1 and word2. You want to convert word1 to word2 using the minimum number of operations. You can perform the following operations on a string:

  1. Insert a character
  2. Delete a character
  3. Replace a character

Return the minimum number of operations required to convert word1 to word2.

Approach

Firstly, we need to realise that there are overlapping subproblems in this problem.

Imagine we’re using 2 pointers — one for each string (say i for word1 and j for word2).

If the characters at the pointers are equal, we can move both pointers forward. If they are not equal, we have 3 options:

  • Replace the character at the first pointer with the character at the second pointer and move both pointers forward.
  • Delete the character at the first pointer and move the first pointer forward.
  • Insert the character at the second pointer into the first string and move the second pointer forward.

Putting this in terms of code:

  • a replacement operation will be dp(i + 1, j + 1) + 1
  • a deletion operation will be dp(i + 1, j) + 1
  • an insertion operation will be dp(i, j + 1) + 1

The + 1 is because we are performing an operation.

Now for the base cases:

  • If we reach the end of both strings, we return 0.
  • If we reach the end of the first string, we return the number of characters left in the second string (which is N - j). This is because we need to insert all the remaining characters of the second string into the first string (since we’ve to convert the first string into the second string).
  • If we reach the end of the second string, we return the number of characters left in the first string (which is M - i). This is because we need to delete all the remaining characters of the first string to convert it into the second string.

And we’re done!

Solution in Python


class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        M = len(word1)
        N = len(word2)
        
        @cache
        def dp(i, j):
            if i >= M and j >= N:
                return 0
            elif i >= M:
                return N - j
            elif j >= N:
                return M - i

            if word1[i] == word2[j]:
                return dp(i + 1, j + 1)
            else:
                return 1 + min(dp(i + 1, j + 1), dp(i + 1, j), dp(i, j + 1))

        return dp(0, 0)

Complexity

  • Time: $O(M \times N)$
    Since we are using memoization, we will only compute the result for each pair of indices (i, j) once. There are M possible values for i (from 0 to M-1) and N possible values for j (from 0 to N-1). Therefore, the total number of unique subproblems is M * N, leading to a time complexity of $O(M \times N)$.

  • Space: $O(M \times N)$
    Since we are using memoization, we will store the results of each subproblem in a cache. The cache will have a size of M * N to store the results for each pair of indices (i, j). Therefore, the space complexity is $O(M \times N)$.

And we are done.