Chapter 10: Transforming One String to Another - Edit Distance

Building directly upon the "Longest Common Subsequence" pattern, we now tackle a more complex string manipulation problem: "Edit Distance." Also known as Levenshtein distance, this algorithm calculates the minimum number of single-character edits (insertions, deletions, or substitutions) required to change one word into another.

This is a powerful and practical algorithm, forming the backbone of features like spell checkers ("Did you mean...?"), computational biology for comparing DNA sequences, and plagiarism detection. We'll use LeetCode problem #72 to explore it. The 2D DP table will once again be our tool, but with richer transitions between states.

The Problem:

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:

1. Insert a character

2. Delete a character

3. Substitute a character

For example:

• word1 = "horse", word2 = "ros" -> The answer is 3.

  1. horse -> rorse (replace 'h' with 'r')

  2. rorse -> rose (delete 'r')

  3. rose -> ros (delete 'e')

Approach 1: The Recursive Solution

Let's define a function solve(i, j) that computes the minimum edit distance between the suffixes word1[i:] and word2[j:].

When comparing word1[i] and word2[j], we have two cases:

1. The characters match: If word1[i] == word2[j], no operation is needed for these characters. We can simply move on to the rest of the strings. The cost is 0, and we solve for solve(i + 1, j + 1).

2. The characters do not match: We must perform one of the three allowed operations. We want the one that leads to the minimum total cost. The cost is 1 (for the operation) plus the cost of the resulting subproblem:

   • Insert: Insert the character word2[j] into word1. Now word1 matches word2 at this position, so we compare word1[i:] with word2[j+1:]. This is 1 + solve(i, j + 1).

   • Delete: Delete the character word1[i]. We now need to match word1[i+1:] with word2[j:]. This is 1 + solve(i + 1, j).

   • Substitute: Replace word1[i] with word2[j]. Both strings are now aligned at this position, so we solve for solve(i + 1, j + 1). This is 1 + solve(i + 1, j + 1).

We take the minimum of these three options. The base case is when we exhaust one string; the cost is the number of characters left in the other string (which must all be inserted or deleted).

def minDistance_recursive(word1: str, word2: str) -> int:

    def solve(i, j):
        # Base case: if one string is empty, we must insert/delete the rest
        if i >= len(word1):
            return len(word2) - j
        if j >= len(word2):
            return len(word1) - i

        if word1[i] == word2[j]:
            return solve(i + 1, j + 1)
        else:
            insert_cost = 1 + solve(i, j + 1)
            delete_cost = 1 + solve(i + 1, j)
            substitute_cost = 1 + solve(i + 1, j + 1)
            return min(insert_cost, delete_cost, substitute_cost)

    return solve(0, 0)

# Trying it out
# print(minDistance_recursive("horse", "ros")) # 3
# print(minDistance_recursive("intention", "execution")) # Very slow

This brute-force recursion is correct but, like LCS, suffers from repeated computations on the same subproblems.

Approach 2: Memoization with a Decorator (Top-Down DP)

The state (i, j) is once again the perfect candidate for caching. Applying our decorator will make this solution efficient.

import functools

class Solution:
    def minDistance_memoized(self, word1: str, word2: str) -> int:

        @functools.lru_cache(maxsize=None)
        def solve(i, j):
            if i >= len(word1):
                return len(word2) - j
            if j >= len(word2):
                return len(word1) - i

            if word1[i] == word2[j]:
                return solve(i + 1, j + 1)
            else:
                insert_cost = 1 + solve(i, j + 1)
                delete_cost = 1 + solve(i + 1, j)
                substitute_cost = 1 + solve(i + 1, j + 1)
                return min(insert_cost, delete_cost, substitute_cost)

        return solve(0, 0)

# Trying it out
# solver = Solution()
# print(solver.minDistance_memoized("intention", "execution")) # 5, and it's fast!

The top-down approach has a time complexity of O(m * n) and clearly expresses the logic of the three operations.

Approach 3: Iteration (Bottom-Up DP)

The bottom-up solution uses a 2D table where dp[i][j] stores the edit distance between word1[:i] and word2[:j].

1. Create a dp table of size (m+1) x (n+1).

2. Initialize Base Cases:

   • The first row dp[0][j] represents converting an empty string to word2[:j], which requires j insertions. So, dp[0][j] = j.

   • The first column dp[i][0] represents converting word1[:i] to an empty string, which requires i deletions. So, dp[i][0] = i.

3. Iterate i from 1 to m and j from 1 to n.

4. Inside the loop, compare word1[i-1] and word2[j-1].

   • If they are the same, no operation is needed. dp[i][j] = dp[i-1][j-1].

   • If they are different, we take the minimum of the three possible operations:

     • dp[i][j-1] (Insert)

     • dp[i-1][j] (Delete)

     • dp[i-1][j-1] (Substitute) And we add 1 for the cost of the operation. So, dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]).

5. The final answer is dp[m][n].

def minDistance_iterative(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Initialize base cases
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

    # Fill the rest of the table
    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][j - 1],    # Insert
                    dp[i - 1][j],    # Delete
                    dp[i - 1][j - 1] # Substitute
                )

    return dp[m][n]

# Trying it out
# print(minDistance_iterative("intention", "execution")) # 5

The bottom-up approach is highly efficient and provides a clear map of the costs for all prefixes, which can be useful for visualizing the solution.

Conclusion

The "Edit Distance" problem is a fantastic example of how a simple DP pattern can be extended to handle more complex scenarios. By building on the 2D grid structure from LCS and adding logic for multiple operations (insert, delete, substitute), you've learned a versatile template that is central to string processing and computational linguistics.