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.
Below are the steps to convert the recursive approach to Bottom up approach:
1. Choosing Dimensions of Table: The state of smaller sub-problems depends on the input parameters m and n because at least one of them will decrease after each recursive call. So we need to construct a 2D table dp[][] to store the solution of the sub-problems.
2. Choosing Correct size of Table: The size of the 2D table will be equal to the total number of different subproblems, which is equal to (m + 1)*(n + 1). As both m and n are decreasing by 1 during the recursive calls and reaching the value 0. So m + 1 possibilities for the first parameter and n + 1 possibilities for the second parameter. Total number of possible subproblems = (m + 1)*(n + 1).
3. Filling the table: It consist of two stages, table initialization and building the solution from the smaller subproblems:
- Table initialization: Before building the solution, we need to initialize the table with the smaller version of the solution i.e. base case. Here m = 0 and n = 0 is the situation of the base case, so we initialize first-column dp[i][0] with i and first-row dp[0][j] with j.
- Building the solution of larger problems from the smaller subproblems: We can easily define the iterative structure by using the recursive structure of the above recursive solution.
- if (str1[i – 1] == str2[j – 1]) dp[i][j] = dp[i – 1][j – 1];
- if (str1[i – 1] != str2[j – 1]) dp[i][j] = 1 + min(dp[i][j – 1], dp[i – 1][j], dp[i – 1][j – 1]);
4. Returning final solution: After filling the table iteratively, our final solution gets stored at the bottom right corner of the 2-D table i.e. we return Edit[m][n] as an output.
Below is the implementation of the above algorithm:
// A Dynamic Programming based C++ program to find minimum
// number operations to convert str1 to str2
#include <bits/stdc++.h>
using namespace std;
// Utility function to find the minimum of three numbers
int min(int x, int y, int z) { return min(min(x, y), z); }
int editDistDP(string str1, string str2, int m, int n)
{
// Create a table to store results of subproblems
int dp[m + 1][n + 1];
// Fill d[][] in bottom up manner
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
// If first string is empty, only option is to
// insert all characters of second string
if (i == 0)
dp[i][j] = j; // Min. operations = j
// If second string is empty, only option is to
// remove all characters of second string
else if (j == 0)
dp[i][j] = i; // Min. operations = i
// If last characters are same, ignore last char
// and recur for remaining string
else if (str1[i - 1] == str2[j - 1])
dp[i][j] = dp[i - 1][j - 1];
// If the last character is different, consider
// all possibilities and find the minimum
else
dp[i][j]
= 1
+ min(dp[i][j - 1], // Insert
dp[i - 1][j], // Remove
dp[i - 1][j - 1]); // Replace
}
}
return dp[m][n];
}
// Driver code
int main()
{
// your code goes here
string str1 = "GEEXSFRGEEKKS";
string str2 = "w3wiki";
cout << editDistDP(str1, str2, str1.length(),
str2.length());
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Utility function to find the minimum of three numbers
int min(int x, int y, int z)
{
if (x <= y && x <= z)
return x;
if (y <= x && y <= z)
return y;
return z;
}
int editDistDP(char* str1, char* str2, int m, int n)
{
// Create a table to store results of subproblems
int dp[m + 1][n + 1];
// Fill d[][] in bottom up manner
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
// If first string is empty, only option is to
// insert all characters of second string
if (i == 0)
dp[i][j] = j; // Min. operations = j
// If second string is empty, only option is to
// remove all characters of second string
else if (j == 0)
dp[i][j] = i; // Min. operations = i
// If last characters are same, ignore last char
// and recur for remaining string
else if (str1[i - 1] == str2[j - 1])
dp[i][j] = dp[i - 1][j - 1];
// If the last character is different, consider
// all possibilities and find the minimum
else
dp[i][j]
= 1
+ min(dp[i][j - 1], // Insert
dp[i - 1][j], // Remove
dp[i - 1][j - 1]); // Replace
}
}
return dp[m][n];
}
// Driver code
int main()
{
char str1[] = "GEEXSFRGEEKKS";
char str2[] = "w3wiki";
int m = strlen(str1);
int n = strlen(str2);
printf("%d\n", editDistDP(str1, str2, m, n));
return 0;
}
// A Dynamic Programming based Java program to find minimum
// number operations to convert str1 to str2
import java.io.*;
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 editDistDP(String str1, String str2, int m,
int n)
{
// Create a table to store results of subproblems
int dp[][] = new int[m + 1][n + 1];
// Fill d[][] in bottom up manner
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
// If first string is empty, only option is
// to insert all characters of second string
if (i == 0)
dp[i][j] = j; // Min. operations = j
// If second string is empty, only option is
// to remove all characters of second string
else if (j == 0)
dp[i][j] = i; // Min. operations = i
// If last characters are same, ignore last
// char and recur for remaining string
else if (str1.charAt(i - 1)
== str2.charAt(j - 1))
dp[i][j] = dp[i - 1][j - 1];
// If the last character is different,
// consider all possibilities and find the
// minimum
else
dp[i][j]
= 1
+ min(
dp[i][j - 1], // Insert
dp[i - 1][j], // Remove
dp[i - 1][j - 1]); // Replace
}
}
return dp[m][n];
}
// Driver Code
public static void main(String args[])
{
String str1 = "GEEXSFRGEEKKS";
String str2 = "w3wiki";
System.out.println(editDistDP(
str1, str2, str1.length(), str2.length()));
}
}
# A Dynamic Programming based Python program for edit
# distance problem
def editDistDP(str1, str2, m, n):
# Create a table to store results of subproblems
dp = [[0 for x in range(n + 1)] for x in range(m + 1)]
# Fill d[][] in bottom up manner
for i in range(m + 1):
for j in range(n + 1):
# If first string is empty, only option is to
# insert all characters of second string
if i == 0:
dp[i][j] = j # Min. operations = j
# If second string is empty, only option is to
# remove all characters of second string
elif j == 0:
dp[i][j] = i # Min. operations = i
# If last characters are same, ignore last char
# and recur for remaining string
elif str1[i-1] == str2[j-1]:
dp[i][j] = dp[i-1][j-1]
# If last character are different, consider all
# possibilities and find minimum
else:
dp[i][j] = 1 + min(dp[i][j-1], # Insert
dp[i-1][j], # Remove
dp[i-1][j-1]) # Replace
return dp[m][n]
# Driver code
str1 = "GEEXSFRGEEKKS"
str2 = "w3wiki"
print(editDistDP(str1, str2, len(str1), len(str2)))
// A Dynamic Programming based
// C# program to find minimum
// number operations 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 editDistDP(String str1, String str2, int m,
int n)
{
// Create a table to store
// results of subproblems
int[, ] dp = new int[m + 1, n + 1];
// Fill d[][] in bottom up manner
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
// If first string is empty, only option is
// to insert all characters of second string
if (i == 0)
// Min. operations = j
dp[i, j] = j;
// If second string is empty, only option is
// to remove all characters of second string
else if (j == 0)
// Min. operations = i
dp[i, j] = i;
// If last characters are same, ignore last
// char and recur for remaining string
else if (str1[i - 1] == str2[j - 1])
dp[i, j] = dp[i - 1, j - 1];
// If the last character is different,
// consider all possibilities and find the
// minimum
else
dp[i, j] = 1
+ min(dp[i, j - 1], // Insert
dp[i - 1, j], // Remove
dp[i - 1,
j - 1]); // Replace
}
}
return dp[m, n];
}
// Driver code
public static void Main()
{
String str1 = "GEEXSFRGEEKKS";
String str2 = "w3wiki";
Console.Write(editDistDP(str1, str2, str1.Length,
str2.Length));
}
}
// A Dynamic Programming based
// Javascript program to find minimum
// number operations 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 editDistDP(str1,str2,m,n)
{
// Create a table to store results of subproblems
let dp = new Array(m + 1);
for(let i=0;i<m+1;i++)
{
dp[i]=new Array(n+1);
for(let j=0;j<n+1;j++)
{
dp[i][j]=0;
}
}
// Fill d[][] in bottom up manner
for (let i = 0; i <= m; i++) {
for (let j = 0; j <= n; j++) {
// If first string is empty, only option is
// to insert all characters of second string
if (i == 0)
dp[i][j] = j; // Min. operations = j
// If second string is empty, only option is
// to remove all characters of second string
else if (j == 0)
dp[i][j] = i; // Min. operations = i
// If last characters are same, ignore last
// char and recur for remaining string
else if (str1[i - 1]
== str2[j - 1])
dp[i][j] = dp[i - 1][j - 1];
// If the last character is different,
// consider all possibilities and find the
// minimum
else
dp[i][j] = 1
+ min(dp[i][j - 1], // Insert
dp[i - 1][j], // Remove
dp[i - 1]
[j - 1]); // Replace
}
}
return dp[m][n];
}
// Driver Code
let str1 = "GEEXSFRGEEKKS";
let str2 = "w3wiki";
console.log(editDistDP(str1, str2, str1.length, str2.length));
Output
3
Time Complexity: O(m x n)
Auxiliary Space: O(m x n)
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.
Contact Us