Table of contents

Edit distance between two strings

Given two strings str1 and str2, find the minimum number of operations required to convert str1 into str2. The allowed operations are:

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

The problem is to calculate the edit distance between the two strings.

Input/Output Examples

plaintext
Example 1:
Input: str1 = "kitten", str2 = "sitting"
Output: 3
Explanation: The minimum operations required are:
Replace k with s
Replace e with i
Insert g at the end

Example 2:
Input: str1 = "sunday", str2 = "saturday"
Output: 3
Explanation: The minimum operations required are:
Insert a after s
Insert t after a
Replace n with r

Approach to find the Edit Distance between two strings

  1. Dynamic Programming Approach:
    • Use a 2D DP table dp[i][j] where i is the index in str1 and j is the index in str2. dp[i][j] represents the minimum edit distance between the first i characters of str1 and the first j characters of str2.
    • If str1[i-1] == str2[j-1], no operation is required, so dp[i][j] = dp[i-1][j-1].
    • If str1[i-1] != str2[j-1], the three possible operations (insert, delete, replace) are considered, and the minimum operation cost is taken:
      • Insert: dp[i][j-1] + 1
      • Delete: dp[i-1][j] + 1
      • Replace: dp[i-1][j-1] + 1
  2. Algorithm:
    • Initialize a DP table of size (len(str1)+1) x (len(str2)+1) where the first row and the first column represent converting one string to an empty string.
    • Traverse through the strings, and for each character pair, update the DP table based on whether the characters match or an operation (insert, delete, replace) is required.
    • The final answer will be stored in dp[len(str1)][len(str2)].
  3. Edge Cases:
    • If either string is empty, the edit distance is the length of the other string (since all characters need to be inserted or deleted).
    • If both strings are equal, the edit distance is 0.

C++ Program to find the Edit Distance between two strings

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

// Function to find the minimum edit distance between two strings
int editDistance(string str1, string str2) {
    int m = str1.length();
    int n = str2.length();

    // Create a DP table with size (m+1) x (n+1)
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));

    // Initialize the base cases
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0) {
                dp[i][j] = j; // If str1 is empty, insert all characters of str2
            } else if (j == 0) {
                dp[i][j] = i; // If str2 is empty, remove all characters of str1
            } else if (str1[i - 1] == str2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1]; // Characters match, no operation needed
            } else {
                // Consider insert, delete, and replace operations
                dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
            }
        }
    }

    // Return the edit distance between the two strings
    return dp[m][n];
}

int main() {
    string str1 = "kitten";
    string str2 = "sitting";

    int result = editDistance(str1, str2);
    cout << "Edit Distance: " << result << endl;

    return 0;
}

Java Program to find the Edit Distance between two strings

cpp
public class EditDistance {

    // Function to find the minimum edit distance between two strings
    public static int editDistance(String str1, String str2) {
        int m = str1.length();
        int n = str2.length();

        // Create a DP table with size (m+1) x (n+1)
        int[][] dp = new int[m + 1][n + 1];

        // Initialize the base cases
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0) {
                    dp[i][j] = j; // If str1 is empty, insert all characters of str2
                } else if (j == 0) {
                    dp[i][j] = i; // If str2 is empty, remove all characters of str1
                } else if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1]; // Characters match, no operation needed
                } else {
                    // Consider insert, delete, and replace operations
                    dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], 
                                            Math.min(dp[i - 1][j], dp[i][j - 1]));
                }
            }
        }

        // Return the edit distance between the two strings
        return dp[m][n];
    }

    public static void main(String[] args) {
        String str1 = "kitten";
        String str2 = "sitting";

        int result = editDistance(str1, str2);
        System.out.println("Edit Distance: " + result);
    }
}

Python Program to find the Edit Distance between two strings

python
# Function to find the minimum edit distance between two strings
def edit_distance(str1, str2):
    m, n = len(str1), len(str2)

    # Create a DP table with size (m+1) x (n+1)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Initialize the base cases
    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0:
                dp[i][j] = j  # If str1 is empty, insert all characters of str2
            elif j == 0:
                dp[i][j] = i  # If str2 is empty, remove all characters of str1
            elif str1[i - 1] == str2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]  # Characters match, no operation needed
            else:
                # Consider insert, delete, and replace operations
                dp[i][j] = 1 + min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])

    # Return the edit distance between the two strings
    return dp[m][n]

# Example usage
if __name__ == "__main__":
    str1 = "kitten"
    str2 = "sitting"
    result = edit_distance(str1, str2)
    print("Edit Distance:", result)

Time Complexity:

  • O(m * n): We compute the values for all entries in the DP table, where m is the length of str1 and n is the length of str2.

Space Complexity:

  • O(m * n): We use a 2D DP table of size (m + 1) x (n + 1).

DSA

Related Articles