Edit Distance

Algorithms

The Edit Distance (Levenshtein distance) problem finds the minimum number of single-character edits (insertions, deletions, or substitutions) required to transform one string into another.

Problem Statement

Given two strings, find the minimum number of operations needed to convert one string into the other, where operations are insert, delete, or substitute a character.

Dynamic Programming Solution

We use dynamic programming where $d p [i] [j]$ represents the edit distance between the first $i$ characters of the first string and the first $j$ characters of the second string.

Time Complexity

The time complexity is $O (mn)$ , where $m$ and $n$ are the lengths of the two strings.

Implementation

def edit_distance(word1, word2):
    """Dynamic Programming approach to find the Edit Distance."""
    m, n = len(word1), len(word2)
    
    # Create a table to store results of subproblems
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Initialize base cases
    for i in range(m + 1):
        dp[i][0] = i  # Deleting all characters from word1 to match empty word2
    for j in range(n + 1):
        dp[0][j] = j  # Inserting all characters into empty word1 to match word2
    
    # Fill the dp 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]  # Characters are the same, no additional cost
            else:
                dp[i][j] = min(dp[i-1][j] + 1,  # Deletion
                               dp[i][j-1] + 1,  # Insertion
                               dp[i-1][j-1] + 1)  # Substitution
    
    return dp[m][n]

# Example usage:
word1 = "intention"
word2 = "execution"
print("Edit distance between '{}' and '{}': {}".format(word1, word2, edit_distance(word1, word2)))  # Output: 5