72.Edit_Distance_(Medium).md

72. Edit Distance (Medium)

Date and Time: Jun 27, 2024, 0:56 (EST)

Link: https://leetcode.com/problems/edit-distance/

Question:

Given two strings word1 and word2, _return the minimum number of operations required to convert word1 to word2_.

You have the following three operations permitted on a word:

• Insert a character
• Delete a character
• Replace a character

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

Walk-through:

DP bottom-up:

In this case, I first create a dP table with an extra row and extra column for base cases. Then I fill out the base cases (bottom row and right-most column), and I fill out the grids by two conditions from the right-bottom corner to the left then go up. In each grid, we set the dP[i][j] to be either dP[i][j] = dP[i+1][j+1] (the diagonal entry) if word1[i] == word2[j]or dP[i][j] = 1 + min(dP[i][j+1], dP[i+1][j], dP[i+1][j+1]) to find the minimum action of Insert (i+1, j), Delete(i, j+1), or Replace(i+1, j+1) with an extra 1.

Note: The first case to update entry does not require 1 operation, because when they match, we can just update both indices to the next indices (when they both match, we should use the previous result, because the # of differences doesn't change). But if we require Insert, Delete, or Replace we perform 1 operation.

Optimized 1d DP:

1. We first initialize the prev for the bottom of the dp table, which should be the distance for word2, so we use a for loop to initialize it.

2. We then initialize dp row for each row with value len(word1) - r, which initialize the whole row to be the distance for current word1 backward.

3. We update dp according to if these two words match or not, and we update prev = dp after loop over the whole columns.

Python DP Solution:

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        #   r o s
        # h 3 3 3 5
        # o 2 2 3 4
        # r 2 2 2 3
        # s 3 2 1 2
        # e 3 2 1 1
        #   3 2 1 0
        
        # DP table: len(word2) * len(word1), build bottom-up
        # r, c for indices of word1 and word2
        # Recurrence Relation:
        # when word1[r] == word2[c]: dp[r-1][c-1]
        # when word1[r] != word2[c]: min(dp[r-1][c], dp[r][c+1], dp[r-1][c-1]) + 1

        # TC: O(m x n), SC:O (m x n)
        rows, cols = len(word1)+1, len(word2)+1
        dp = [[0] * (len(word2)+1) for _ in range(len(word1)+1)]
        # Base case for last col
        for r in range(len(word1)-1, -1, -1):
            dp[r][-1] = dp[r+1][-1] + 1
        # Base case for last row
        for c in range(len(word2)-1, -1, -1):
            dp[-1][c] = dp[-1][c+1] + 1
        
        # Fill out the recurrence relation
        for r in range(rows-2, -1, -1):
            for c in range(cols-2, -1, -1):
                if word1[r] == word2[c]:
                    dp[r][c] = dp[r+1][c+1]
                else:
                    dp[r][c] = min(dp[r+1][c], dp[r][c+1], dp[r+1][c+1]) + 1

        return dp[0][0]

Time Complexity: $O(m * n)$, m is the length of word1, n is the length of word2.
Space Complexity: $O(m * n)$, because we are storing the 2d DP table.

Optimized DP Solution:

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        #   r o s
        # h 3 3 3 5
        # o 2 2 3 4
        # r 2 2 2 3
        # s 3 2 1 2
        # e 3 2 1 1
        #   3 2 1 0
        
        # DP table: len(word2) * len(word1), build bottom-up
        # r, c for indices of word1 and word2
        # Recurrence Relation:
        # when word1[r] == word2[c]: dp[r-1][c-1]
        # when word1[r] != word2[c]: min(dp[r-1][c], dp[r][c+1], dp[r-1][c-1]) + 1

        # TC: O(m x n), SC: O(n)
        rows, cols = len(word1)+1, len(word2)+1
        dp = [0] * (len(word2)+1)
        # Base case for last row
        for c in range(cols-2, -1, -1):
            dp[c] = dp[c+1] + 1

        # Fill out the recurrence relation
        for r in range(rows-2, -1, -1):
            prev = dp.copy()   # Copy of the previous row
            dp[cols-1] = prev[cols-1] + 1   # Update the last entry
            for c in range(cols-2, -1, -1):
                if word1[r] == word2[c]:
                    dp[c] = prev[c+1]
                else:
                    dp[c] = min(prev[c], dp[c+1], prev[c+1]) + 1
            
        return dp[0]

Time Complexity: $O(m * n)$, m is the length of word1, n is the length of word2.
Space Complexity: $O(n)$, because we only store one row.