Edit Distance In C,CPP,JAVA,PYTHON,C#,JS

/ DSA / By
Spread the love
Close-up of a computer screen displaying programming code in a dark environment.

Problem Statement: Edit Distance

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. You have the following three operations available:

  1. Insert a character.
  2. Delete a character.
  3. Replace a character.

Example 1:

Input:

word1 = "horse", word2 = "ros"

Output:

3

Explanation: The minimum number of operations required to convert “horse” to “ros” is:

  • “horse” → “ros” (remove ‘h’)
  • “ros” → “ros” (no change)
  • “ros” → “ros” (no change)

Thus, the answer is 3.

Example 2:

Input:

word1 = "intention", word2 = "execution"

Output:

5

Explanation: The minimum number of operations required to convert “intention” to “execution” is:

  1. “intention” → “intexion” (replace ‘t’ with ‘x’)
  2. “intexion” → “extexion” (replace ‘i’ with ‘e’)
  3. “extexion” → “excexion” (replace ‘t’ with ‘c’)
  4. “excexion” → “executin” (replace ‘x’ with ‘u’)
  5. “executin” → “execution” (insert ‘o’)

Thus, the answer is 5.

Approach:

This problem can be solved using Dynamic Programming (DP), where we build a table dp[i][j] to store the minimum edit distance between the first i characters of word1 and the first j characters of word2.

DP Table Definition:

  • Let dp[i][j] represent the minimum number of operations required to convert the first i characters of word1 to the first j characters of word2.

Recurrence Relation:

  1. Base Case:
    • If word1 is empty (i = 0), the only option is to insert all characters from word2, so dp[0][j] = j.
    • If word2 is empty (j = 0), the only option is to delete all characters from word1, so dp[i][0] = i.
  2. State Transition:
    • If the characters word1[i-1] and word2[j-1] are the same, no operation is needed, so: dp[i][j]=dp[i−1][j−1]dp[i][j] = dp[i-1][j-1]dp[i][j]=dp[i−1][j−1]
    • Otherwise, we can perform one of the following operations:
      • Insert a character: dp[i][j-1] + 1
      • Delete a character: dp[i-1][j] + 1
      • Replace a character: dp[i-1][j-1] + 1
    • Thus, the recurrence relation is: dp[i][j]=min⁡(dp[i−1][j−1]+1,dp[i][j−1]+1,dp[i−1][j]+1)dp[i][j] = \min(dp[i-1][j-1] + 1, dp[i][j-1] + 1, dp[i-1][j] + 1)dp[i][j]=min(dp[i−1][j−1]+1,dp[i][j−1]+1,dp[i−1][j]+1)
  3. Final Answer:
    • The answer is stored in dp[len(word1)][len(word2)].

Time and Space Complexity:

  • Time Complexity: O(m * n), where m and n are the lengths of word1 and word2, respectively. We need to fill a table of size m * n.
  • Space Complexity: O(m * n) for the DP table. This can be optimized to O(min(m, n)) by using only two rows.

Code Implementations in Different Languages:

1. C Language (DP Approach):

#include <stdio.h>
#include <string.h>

int min(int a, int b, int c) {
    if (a <= b && a <= c) return a;
    if (b <= a && b <= c) return b;
    return c;
}

int minDistance(char* word1, char* word2) {
    int m = strlen(word1), n = strlen(word2);
    int dp[m + 1][n + 1];
    
    // Initialize base cases
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    
    // Fill the dp table
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1;
            }
        }
    }
    
    return dp[m][n];
}

int main() {
    char word1[] = "horse";
    char word2[] = "ros";
    printf("Edit Distance: %d\n", minDistance(word1, word2));  // Output: 3
    return 0;
}

2. C++ Language (DP Approach):

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int minDistance(string word1, string word2) {
    int m = word1.length(), n = word2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));

    // Initialize base cases
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;

    // Fill the dp table
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = min({dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]}) + 1;
            }
        }
    }

    return dp[m][n];
}

int main() {
    string word1 = "horse", word2 = "ros";
    cout << "Edit Distance: " << minDistance(word1, word2) << endl;  // Output: 3
    return 0;
}

3. Java (DP Approach):

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

        // Initialize base cases
        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;

        // Fill the dp table
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
                }
            }
        }

        return dp[m][n];
    }

    public static void main(String[] args) {
        String word1 = "horse", word2 = "ros";
        System.out.println("Edit Distance: " + minDistance(word1, word2));  // Output: 3
    }
}

4. Python (DP Approach):

def minDistance(word1, word2):
    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 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]
            else:
                dp[i][j] = min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j])) + 1

    return dp[m][n]

# Test case
word1 = "horse"
word2 = "ros"
print(f"Edit Distance: {minDistance(word1, word2)}")  # Output: 3

5. C# (DP Approach):

using System;

class Program {
    public static int MinDistance(string word1, string word2) {
        int m = word1.Length, n = word2.Length;
        int[,] dp = new int[m + 1, n + 1];

        // Initialize base cases
        for (int i = 0; i <= m; i++) dp[i, 0] = i;
        for (int j = 0; j <= n; j++) dp[0, j] = j;

        // Fill the dp table
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i, j] = dp[i - 1, j - 1];
                } else {
                    dp[i, j] = Math.Min(dp[i - 1, j - 1], Math.Min(dp[i, j - 1], dp[i - 1, j])) + 1;
                }
            }
        }

        return dp[m, n];
    }

    static void Main() {
        string word1 = "horse", word2 = "ros";
        Console.WriteLine($"Edit Distance: {MinDistance(word1, word2)}");  // Output: 3
    }
}

6. JavaScript (DP Approach):

function minDistance(word1, word2) {
    let m = word1.length, n = word2.length;
    let dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));

    // Initialize base cases
    for (let i = 0; i <= m; i++) dp[i][0] = i;
    for (let j = 0; j <= n; j++) dp[0][j] = j;

    // Fill the dp table
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (word1[i - 1] === word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
            }
        }
    }

    return dp[m][n];
}

// Test case
let word1 = "horse", word2 = "ros";
console.log(`Edit Distance: ${minDistance(word1, word2)}`);  // Output: 3

Complexity Analysis:

Time Complexity:

  • Time Complexity: O(m * n), where m is the length of word1 and n is the length of word2. We need to fill a table of size m * n.

Space Complexity:

  • Space Complexity: O(m * n) for the DP table. This can be optimized to O(min(m, n)) by using two rows.

Conclusion:

The Edit Distance problem can be efficiently solved using dynamic programming. By building a table and applying the recurrence relation, we can compute the minimum number of operations required to transform one string into another. This solution runs in O(m * n) time with O(m * n) space complexity, where m and n are the lengths of the input strings.