Home Data Structures and Algorithms Edit Distance using Recursion

Edit Distance using Recursion

Edit Distance Using Dynamic Programming (Memoization):

Subproblems in Edit Distance:

The idea is to process all characters one by one starting from either from left or right sides of both strings. 
Let us process from the right end of the strings, there are two possibilities for every pair of characters being traversed, either they match or they don’t match. If last characters of both string matches then there is no need to perform any operation So, recursively calculate the answer for rest of part of the strings. When last characters do not match, we can perform all three operations to match the last characters in the given strings, i.e. insert, replace, and remove. We then recursively calculate the result for the remaining part of the string. Upon completion of these operations, we will select the minimum answer.

Below is the recursive tree for this problem:

When the last characters of strings matches. Make a recursive call EditDistance(M-1,N-1) to calculate the answer for remaining part of the strings.

When the last characters of strings don’t matches. Make three recursive calls as show below:

  • Insert str1[N-1] at last of str2 : EditDistance(M, N-1)
  • Replace str2[M-1] with str1[N-1] : EditDistance(M-1, N-1)
  • Remove str2[M-1] : EditDistance(M-1, N)

Recurrence Relations for Edit Distance:

  • EditDistance(str1, str2, M, N) = EditDistance(str1, str2, M-1, N-1)
  • Case 1: When the last character of both the strings are same
  • Case 2: When the last characters are different
    • EditDistance(str1, str2, M, N) = 1 + Minimum{ EditDistance(str1, str2 ,M-1,N-1), EditDistance(str1, str2 ,M,N-1), EditDistance(str1, str2 ,M-1,N) }

Base Case for Edit Distance:

  • Case 1: When str1 becomes empty i.e. M=0
    • return N, as it require N characters to convert an empty string to str1 of size N
  • Case 2: When str2 becomes empty i.e. N=0
    • return M, as it require M characters to convert an empty string to str2 of size M

Below is the implementation of the above recursive solution.

C++ 
// A Naive recursive C++ program to find minimum number
// operations to convert str1 to str2
#include <bits/stdc++.h>
using namespace std;

// Utility function to find minimum of three numbers
int min(int x, int y, int z) { return min(min(x, y), z); }

int editDist(string str1, string str2, int m, int n)
{
    // If first string is empty, the only option is to
    // insert all characters of second string into first
    if (m == 0)
        return n;

    // If second string is empty, the only option is to
    // remove all characters of first string
    if (n == 0)
        return m;

    // If last characters of two strings are same, nothing
    // much to do. Get the count for
    // remaining strings.
    if (str1[m - 1] == str2[n - 1])
        return editDist(str1, str2, m - 1, n - 1);

    // If last characters are not same, consider all three
    // operations on last character of first string,
    // recursively compute minimum cost for all three
    // operations and take minimum of three values.
    return 1
           + min(editDist(str1, str2, m, n - 1), // Insert
                 editDist(str1, str2, m - 1, n), // Remove
                 editDist(str1, str2, m - 1,
                          n - 1) // Replace
           );
}

// Driver code
int main()
{
    // your code goes here
    string str1 = "GEEXSFRGEEKKS";
    string str2 = "w3wiki";

    cout << editDist(str1, str2, str1.length(),
                     str2.length());

    return 0;
}
C 
// A Naive recursive C program to find minimum number
// operations to convert str1 to str2
#include <stdio.h>
#include <string.h>

// Utility function to find minimum of three numbers
int min(int x, int y, int z)
{
    return x < y ? (x < z ? x : z) : (y < z ? y : z);
}

int editDist(char* str1, char* str2, int m, int n)
{
    // If first string is empty, the only option is to
    // insert all characters of second string into first
    if (m == 0)
        return n;

    // If second string is empty, the only option is to
    // remove all characters of first string
    if (n == 0)
        return m;

    // If last characters of two strings are same, nothing
    // much to do. Get the count for
    // remaining strings.
    if (str1[m - 1] == str2[n - 1])
        return editDist(str1, str2, m - 1, n - 1);

    // If last characters are not same, consider all three
    // operations on last character of first string,
    // recursively compute minimum cost for all three
    // operations and take minimum of three values.
    return 1
           + min(
               editDist(str1, str2, m, n - 1), // Insert
               editDist(str1, str2, m - 1, n), // Remove
               editDist(str1, str2, m - 1, n - 1) // Replace
           );
}

// Driver code
int main()
{ 
      // your code goes here
    char str1[] = "GEEXSFRGEEKKS";
    char str2[] = "w3wiki";
    int m = strlen(str1);
    int n = strlen(str2);

    printf("%d", editDist(str1, str2, m, n));

    return 0;
}
Java 
// A Naive recursive Java program to find minimum number
// operations to convert str1 to str2
class EDIST {
    static int min(int x, int y, int z)
    {
        if (x <= y && x <= z)
            return x;
        if (y <= x && y <= z)
            return y;
        else
            return z;
    }

    static int editDist(String str1, String str2, int m,
                        int n)
    {
        // If first string is empty, the only option is to
        // insert all characters of second string into first
        if (m == 0)
            return n;

        // If second string is empty, the only option is to
        // remove all characters of first string
        if (n == 0)
            return m;

        // If last characters of two strings are same,
        // nothing much to do. Get the count for remaining
        // strings.
        if (str1.charAt(m - 1) == str2.charAt(n - 1))
            return editDist(str1, str2, m - 1, n - 1);

        // If last characters are not same, consider all
        // three operations on last character of first
        // string, recursively compute minimum cost for all
        // three operations and take minimum of three
        // values.
        return 1
            + min(editDist(str1, str2, m, n - 1), // Insert
                  editDist(str1, str2, m - 1, n), // Remove
                  editDist(str1, str2, m - 1,
                           n - 1) // Replace
            );
    }

    // Driver Code
    public static void main(String args[])
    {
        String str1 = "GEEXSFRGEEKKS";
        String str2 = "w3wiki";

        System.out.println(editDist(
            str1, str2, str1.length(), str2.length()));
    }
}
Python3 
# A Naive recursive Python program to find minimum number
# operations to convert str1 to str2


def editDistance(str1, str2, m, n):

    # If first string is empty, the only option is to
    # insert all characters of second string into first
    if m == 0:
        return n

    # If second string is empty, the only option is to
    # remove all characters of first string
    if n == 0:
        return m

    # If last characters of two strings are same, nothing
    # much to do. Ignore last characters and get count for
    # remaining strings.
    if str1[m-1] == str2[n-1]:
        return editDistance(str1, str2, m-1, n-1)

    # If last characters are not same, consider all three
    # operations on last character of first string, recursively
    # compute minimum cost for all three operations and take
    # minimum of three values.
    return 1 + min(editDistance(str1, str2, m, n-1),    # Insert
                   editDistance(str1, str2, m-1, n),    # Remove
                   editDistance(str1, str2, m-1, n-1)    # Replace
                   )


# Driver code
str1 = "GEEXSFRGEEKKS"
str2 = "w3wiki"
print(editDistance(str1, str2, len(str1), len(str2)))
C# 
// A Naive recursive C# program to
// find minimum numberoperations
// to convert str1 to str2
using System;

class GFG {
    static int min(int x, int y, int z)
    {
        if (x <= y && x <= z)
            return x;
        if (y <= x && y <= z)
            return y;
        else
            return z;
    }

    static int editDist(String str1, String str2, int m,
                        int n)
    {
        // If first string is empty, the only option is to
        // insert all characters of second string into first
        if (m == 0)
            return n;

        // If second string is empty, the only option is to
        // remove all characters of first string
        if (n == 0)
            return m;

        // If last characters of two strings are same,
        // nothing much to do.Get the count for remaining
        // strings.
        if (str1[m - 1] == str2[n - 1])
            return editDist(str1, str2, m - 1, n - 1);

        // If last characters are not same, consider all
        // three operations on last character of first
        // string, recursively compute minimum cost for all
        // three operations and take minimum of three
        // values.
        return 1
            + min(editDist(str1, str2, m, n - 1), // Insert
                  editDist(str1, str2, m - 1, n), // Remove
                  editDist(str1, str2, m - 1,
                           n - 1) // Replace
            );
    }

    // Driver code
    public static void Main()
    {
        String str1 = "GEEXSFRGEEKKS";
        String str2 = "w3wiki";
        Console.WriteLine(
            editDist(str1, str2, str1.Length, str2.Length));
    }
}
JavaScript 
// Javascript program to
// find minimum numberoperations
// to convert str1 to str2
function min(x, y, z)
{
    if (x <= y && x <= z)
        return x;
    if (y <= x && y <= z)
        return y;
    else
        return z;
}

function editDist(str1, str2, m, n)
{
    
    // If first string is empty, the 
    // only option is to insert all 
    // characters of second string into first
    if (m == 0)
        return n;

    // If second string is empty, the only
    // option is to remove all characters 
    // of first string
    if (n == 0)
        return m;

    // If last characters of two strings are
    // same, nothing much to do. Get the count for remaining 
    // strings.
    if (str1[m - 1] == str2[n - 1])
        return editDist(str1, str2, m - 1, n - 1);

    // If last characters are not same, consider all
    // three operations on last character of first
    // string, recursively compute minimum cost for all
    // three operations and take minimum of three
    // values.
    return 1 + 
    min(editDist(str1, str2, m, n - 1), // Insert
        editDist(str1, str2, m - 1, n), // Remove
        editDist(str1, str2, m - 1, n - 1)); // Replace
}

// Driver code
let str1 = "GEEXSFRGEEKKS";
let str2 = "w3wiki";
console.log(editDist(str1, str2, str1.length, 
                                    str2.length));

Output
3

Time Complexity: O(3^m), when length of “str1” >= length of “str2” and O(3^n), when length of “str2” > length of “str1”. Here m=length of “str1 and n=length of “str2”
Auxiliary Space: O(m), when length of “str1” >= length of “str2” and O(n), when length of “str2” > length of “str1”. Here m=length of “str1 and n=length of “str2”

Edit Distance

Given two strings str1 and str2 of length M and N respectively and below operations that can be performed on str1. Find the minimum number of edits (operations) to convert ‘str1‘ into ‘str2‘.  

  • Operation 1 (INSERT): Insert any character before or after any index of str1
  • Operation 2 (REMOVE): Remove a character of str1
  • Operation 3 (Replace): Replace a character at any index of str1 with some other character.

Note: All of the above operations are of equal cost. 

Examples: 

Input:   str1 = “geek”, str2 = “gesek”
Output:  1
Explanation: We can convert str1 into str2 by inserting a ‘s’ between two consecutive ‘e’ in str2.

Input:   str1 = “cat”, str2 = “cut”
Output:  1
Explanation: We can convert str1 into str2 by replacing ‘a’ with ‘u’.

Input:   str1 = “sunday”, str2 = “saturday”
Output:  3
Explanation: Last three and first characters are same.  We basically need to convert “un” to “atur”.  This can be done using below three operations. Replace ‘n’ with ‘r’, insert t, insert a

Illustration of Edit Distance:

Let’s suppose we have str1=”GEEXSFRGEEKKS” and str2=”w3wiki”
Now to convert str1 into str2 we would require 3 minimum operations:
Operation 1: Replace ‘X‘ to ‘K‘
Operation 2: Insert ‘O‘ between ‘F‘ and ‘R‘
Operation 3: Remove second last character i.e. ‘K‘

Refer the below image for better understanding.

Recommended Practice
Edit Distance
Try It!

Similar Reads

Edit Distance using Recursion:

Subproblems in Edit Distance:...

Edit Distance Using Dynamic Programming (Memoization):

In the above recursive approach, there are several overlapping subproblems:Edit_Distance(M-1, N-1) is called Three times Edit_Distance(M-1, N-2) is called Two times Edit_Distance(M-2, N-1) is called Two times. And so on… So, we can use Memoization technique to store the result of each subproblems to avoid recalculating the result again and again. Below are the illustration of overlapping subproblems during the recursion....

Edit Distance Using Dynamic Programming (Bottom-Up Approach):

Use a table to store solutions of subproblems to avoiding recalculate the same subproblems multiple times. By doing this, if same subproblems repeated during, we retrieve the solutions from the table itself....

Edit Distance Using Dynamic Programming (Optimization in Space Complexity):

Optimized Space Complexity Solution: In the above bottom up approach we require O(m x n) space. Let’s take an observation and try to optimize our space complexity: To fill a row in DP array we require only one row i.e. the upper row. For example, if we are filling the row where i=10 in DP array then we require only values of 9th row. So we simply create a DP array of 2 x str1 length. This approach reduces the space complexity from O(N*M) to O(2*N)....

Edit Distance Using Dynamic Programming (Further Optimization in Space Complexity):

As discussed the above approach uses two 1-D arrays, now the question is can we achieve our task by using only a single 1-D array? The answer is Yes and it requires a simple observation as mentioned below:In the previous approach The curr[] array is updated using 3 values only : Value 1: curr[j] = prev[j-1] when str1[i-1] is equal to str2[j-1]Value 2: curr[j] = prev[j] when str1[i-1] is not equal to str2[j-1] Value 3: curr[j] = curr[j-1] when str1[i-1] is not equal to str2[j-1] By keeping the track of these three values we can achiever our task using only a single 1-D array...

Real-World Applications of Edit Distance:

Spell Checking and Auto-CorrectionDNA Sequence AlignmentPlagiarism DetectionNatural Language ProcessingVersion Control SystemsString Matching...

Tags:
#Amazon #edit-distance #DSA #Dynamic Programming #Amazon #Dynamic Programming

Edit Distance Using Dynamic Programming (Memoization):

Contact Us

Categories
Learn the most popular programming languages in the world.