Edit Distance

72.Edit Distance

String

Dynamic Programming

Problem Statement:

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. You have three operations permitted: insert a character, delete a character, or replace a character.

Example:

Input:

word1 = "horse" word2 = "ros"

→

Output:

3

Explanation:
horse → rorse (replace 'h' with 'r')
rorse → rose (delete 'r')
rose → ros (delete 'e')

Algorithm:

1. Create DP table where dp[i][j] represents minimum operations needed to transform word1[0...i] to word2[0...j]
2. Initialize base cases: empty string transformations
3. For each character pair, if they match, copy diagonal value
4. If they don't match, take minimum of insert, delete, or replace operations and add 1
5. Final cell contains minimum operations for entire strings

Complexity:

Time: O(m×n) | Space: O(m×n)

Java Solution:

public int minDistance(String word1, String word2) {
    int[][] dp = new int[word1.length() + 1][word2.length() + 1];

    // Base cases: transforming to/from empty string
    for (int i = 0; i < dp.length; i++) dp[i][0] = i;
    for (int j = 0; j < dp[0].length; j++) dp[0][j] = j;

    // Fill DP table
    for (int i = 1; i < dp.length; i++) 
        for (int j = 1; j < dp[0].length; j++) 
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) 
                dp[i][j] = dp[i - 1][j - 1];  // Characters match
            else 
                dp[i][j] = min(dp[i - 1][j],     // Delete
                             dp[i][j - 1],     // Insert
                             dp[i - 1][j - 1]  // Replace
                             ) + 1;

    return dp[word1.length()][word2.length()];
}

public int min(int a, int b, int c) {
    return Math.min(a, Math.min(b, c));
}

Python Solution:

def minDistance(self, word1: str, word2: str) -> int:
    dp = [[0] * (len(word2) + 1) for _ in range(len(word1) + 1)]
    
    # Base cases: transforming to/from empty string
    for i in range(len(word1) + 1):
        dp[i][0] = i
    for j in range(len(word2) + 1):
        dp[0][j] = j
    
    # Fill DP table
    for i in range(1, len(word1) + 1):
        for j in range(1, len(word2) + 1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]  # Characters match
            else:
                dp[i][j] = min(dp[i-1][j],    # Delete
                              dp[i][j-1],    # Insert
                              dp[i-1][j-1] # Replace
                              ) + 1
    
    return dp[-1][-1]

C++ Solution:

int minDistance(string word1, string word2) {
    vector<vector<int>> dp(word1.length() + 1, 
                              vector<int>(word2.length() + 1));
    
    // Base cases: transforming to/from empty string
    for (int i = 0; i < dp.size(); i++) 
        dp[i][0] = i;
    for (int j = 0; j < dp[0].size(); j++) 
        dp[0][j] = j;
    
    // Fill DP table
    for (int i = 1; i < dp.size(); i++) 
        for (int j = 1; j < dp[0].size(); j++) 
            if (word1[i-1] == word2[j-1]) 
                dp[i][j] = dp[i-1][j-1];  // Characters match
            else 
                dp[i][j] = min({dp[i-1][j],    // Delete
                               dp[i][j-1],    // Insert
                               dp[i-1][j-1] // Replace
                              }) + 1;
    
    return dp[word1.length()][word2.length()];
}