72. Edit Distance - Explanation

Description

You are given two strings word1 and word2, each consisting of lowercase English letters.

You are allowed to perform three operations on word1 an unlimited number of times:

Insert a character at any position
Delete a character at any position
Replace a character at any position

Return the minimum number of operations to make word1 equal word2.

Example 1:

Input: word1 = "monkeys", word2 = "money"

Output: 2

Explanation:
monkeys -> monkey (remove s)
monkey -> money (remove k)

Example 2:

Input: word1 = "neatcdee", word2 = "neetcode"

Output: 3

Explanation:
neatcdee -> neetcdee (replace a with e)
neetcdee -> neetcde (remove last e)
neetcde -> neetcode (insert o)

Constraints:

0 <= word1.length, word2.length <= 100
word1 and word2 consist of lowercase English letters.

Recommended Time & Space Complexity

You should aim for a solution as good or better than O(m * n) time and O(m * n) space, where m and n are the lengths of the strings word1 and word2, respectively.

Hint 1

Try to think in terms of recursion and visualize it as a decision tree, as we have choices at each recursion step. Can you determine the recurrence relation and base cases?

Hint 2

We recursively iterate through the strings using indices i and j for word1 and word2, respectively. If the characters at the current indices match, we increment both indices without counting an operation. Otherwise, we have three choices: insert the character at the current index of word1 (increment j), delete the current character of word1 (increment i), or replace the character at index i in word1 (increment both i and j).

Hint 3

If index i goes out of bounds, we return the number of remaining characters in word2 (using insert operations). If index j goes out of bounds, we return the number of remaining characters in word1 (using delete operations). At each step, we return the minimum operation path. This approach is exponential. Can you think of a way to optimize it?

Hint 4

We can use memoization to cache the results and avoid redundant calculations. A hash map or a 2D array can be used to store these results.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Recursion

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)

        def dfs(i, j):
            if i == m:
                return n - j
            if j == n:
                return m - i
            if word1[i] == word2[j]:
                return dfs(i + 1, j + 1)
            res = min(dfs(i + 1, j), dfs(i, j + 1))
            res = min(res, dfs(i + 1, j + 1))
            return res + 1

        return dfs(0, 0)

Time & Space Complexity

Time complexity: $O(3 ^ {m + n})$
Space complexity: $O(m + n)$

Where $m$ is the length of $word1$ and $n$ is the length of $word2$ .

2. Dynamic Programming (Top-Down)

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)

        dp = {}
        def dfs(i, j):
            if i == m:
                return n - j
            if j == n:
                return m - i
            if (i, j) in dp:
                return dp[(i, j)]

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

        return dfs(0, 0)

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(m * n)$

Where $m$ is the length of $word1$ and $n$ is the length of $word2$ .

3. Dynamic Programming (Bottom-Up)

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [[float("inf")] * (len(word2) + 1) for i in range(len(word1) + 1)]

        for j in range(len(word2) + 1):
            dp[len(word1)][j] = len(word2) - j
        for i in range(len(word1) + 1):
            dp[i][len(word2)] = len(word1) - i

        for i in range(len(word1) - 1, -1, -1):
            for j in range(len(word2) - 1, -1, -1):
                if word1[i] == word2[j]:
                    dp[i][j] = dp[i + 1][j + 1]
                else:
                    dp[i][j] = 1 + min(dp[i + 1][j], dp[i][j + 1], dp[i + 1][j + 1])
        return dp[0][0]

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(m * n)$

Where $m$ is the length of $word1$ and $n$ is the length of $word2$ .

4. Dynamic Programming (Space Optimized)

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        if m < n:
            m, n = n, m
            word1, word2 = word2, word1

        dp = [0] * (n + 1)
        nextDp = [0] * (n + 1)

        for j in range(n + 1):
            dp[j] = n - j

        for i in range(m - 1, -1, -1):
            nextDp[n] = m - i
            for j in range(n - 1, -1, -1):
                if word1[i] == word2[j]:
                    nextDp[j] = dp[j + 1]
                else:
                    nextDp[j] = 1 + min(dp[j], nextDp[j + 1], dp[j + 1])
            dp = nextDp[:]

        return dp[0]

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(min(m, n))$

Where $m$ is the length of $word1$ and $n$ is the length of $word2$ .

5. Dynamic Programming (Optimal)

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        if m < n:
            m, n = n, m
            word1, word2 = word2, word1

        dp = [n - i for i in range(n + 1)]

        for i in range(m - 1, -1, -1):
            nextDp = dp[n]
            dp[n] = m - i
            for j in range(n - 1, -1, -1):
                temp = dp[j]
                if word1[i] == word2[j]:
                    dp[j] = nextDp
                else:
                    dp[j] = 1 + min(dp[j], dp[j + 1], nextDp)
                nextDp = temp
        return dp[0]

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(min(m, n))$

Where $m$ is the length of $word1$ and $n$ is the length of $word2$ .