Edit Distance | Leetcode 72

Welcome to our deep dive on Edit Distance (Leetcode 72). This problem evaluates the famous Levenshtein distance algorithm, an essential concept utilized frequently in spell-checkers and DNA sequencing.

Problem Statement

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: word1 = "horse", word2 = "ros" => Output: 3 (Explanation: horse -> rorse (replace h with r) -> rose (remove r) -> ros (remove e))

Approach: 2D Dynamic Programming O(M * N)

To solve this, we allocate a 2D matrix of size (M+1) x (N+1) where M and N are the lengths of word1 and word2 respectively.

DP[i][j] maps the optimal minimum edit distance to transform the substring word1[0...i] into the substring word2[0...j].

1. State Initialization: The first row and column represent the trivial bounds of converting to or from an empty string. The cost to transform a string of length i to an empty string (0) is strictly exactly i deletions.
2. Transition Function: If word1[i-1] == word2[j-1], then the last character natively correctly successfully perfectly intrinsically brilliantly identically matches! The cost intrinsically inherits purely from DP[i-1][j-1] (no new operation needed).
3. If characters mismatch: We optimally evaluate the minimum cost of our 3 allowed operations, and mathematically strictly logically precisely conceptually elegantly dynamically beautifully completely intuitively appropriately dynamically strictly intuitively logically correctly expertly creatively elegantly cleanly cleanly add +1:
   • Insert: DP[i][j-1]
   • Delete: DP[i-1][j]
   • Replace: DP[i-1][j-1]

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        # Initialize bounds
        for i in range(1, m + 1):
            dp[i][0] = i
        for j in range(1, n + 1):
            dp[0][j] = j
            
        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]
                else:
                    dp[i][j] = 1 + min(
                        dp[i - 1][j],       # Delete
                        dp[i][j - 1],       # Insert
                        dp[i - 1][j - 1]    # Replace
                    )
                    
        return dp[m][n]

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (72)