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.
Below is the implementation of Edit Distance Using Dynamic Programming (Memoization):
#include <bits/stdc++.h>
using namespace std;
int minDis(string s1, string s2, int n, int m,
vector<vector<int> >& dp)
{
// If any string is empty,
// return the remaining characters of other string
if (n == 0)
return m;
if (m == 0)
return n;
// To check if the recursive tree
// for given n & m has already been executed
if (dp[n][m] != -1)
return dp[n][m];
// If characters are equal, execute
// recursive function for n-1, m-1
if (s1[n - 1] == s2[m - 1]) {
return dp[n][m] = minDis(s1, s2, n - 1, m - 1, dp);
}
// If characters are nt equal, we need to
// find the minimum cost out of all 3 operations.
// 1. insert 2.delete 3.replace
else {
int insert, del, replace; // temp variables
insert = minDis(s1, s2, n, m - 1, dp);
del = minDis(s1, s2, n - 1, m, dp);
replace = minDis(s1, s2, n - 1, m - 1, dp);
return dp[n][m]
= 1 + min(insert, min(del, replace));
}
}
// Driver program
int main()
{
string str1 = "GEEXSFRGEEKKS";
string str2 = "w3wiki";
int n = str1.length(), m = str2.length();
vector<vector<int> > dp(n + 1, vector<int>(m + 1, -1));
cout << minDis(str1, str2, n, m, dp);
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int min(int x, int y, int z)
{
if (x < y && x < z)
return x;
else if (y < x && y < z)
return y;
else
return z;
}
int minDis(char* s1, char* s2, int n, int m)
{
int dp[n + 1][m + 1];
// Fill dp[][] table in bottom up manner
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
// If first string is empty, only option is to
// insert all characters of second string
if (i == 0)
dp[i][j] = j;
// If second string is empty, only option is to
// remove all characters of second string
else if (j == 0)
dp[i][j] = i;
// If last characters are same, ignore last char
// and recur for remaining string
else if (s1[i - 1] == s2[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[n][m];
}
int main()
{
char* str1 = "GEEXSFRGEEKKS";
char* str2 = "w3wiki";
int n = strlen(str1), m = strlen(str2);
printf("%d", minDis(str1, str2, n, m));
return 0;
}
import java.util.*;
class GFG {
static int minDis(String s1, String s2, int n, int m,
int[][] dp)
{
// If any String is empty,
// return the remaining characters of other String
if (n == 0)
return m;
if (m == 0)
return n;
// To check if the recursive tree
// for given n & m has already been executed
if (dp[n][m] != -1)
return dp[n][m];
// If characters are equal, execute
// recursive function for n-1, m-1
if (s1.charAt(n - 1) == s2.charAt(m - 1)) {
return dp[n][m]
= minDis(s1, s2, n - 1, m - 1, dp);
}
// If characters are nt equal, we need to
// find the minimum cost out of all 3 operations.
else {
int insert, del, replace; // temp variables
insert = minDis(s1, s2, n, m - 1, dp);
del = minDis(s1, s2, n - 1, m, dp);
replace = minDis(s1, s2, n - 1, m - 1, dp);
return dp[n][m]
= 1
+ Math.min(insert,
Math.min(del, replace));
}
}
// Driver program
public static void main(String[] args)
{
String str1 = "GEEXSFRGEEKKS";
String str2 = "w3wiki";
int n = str1.length(), m = str2.length();
int[][] dp = new int[n + 1][m + 1];
for (int i = 0; i < n + 1; i++)
Arrays.fill(dp[i], -1);
System.out.print(minDis(str1, str2, n, m, dp));
}
}
def minDis(s1, s2, n, m, dp):
# If any string is empty,
# return the remaining characters of other string
if(n == 0):
return m
if(m == 0):
return n
# To check if the recursive tree
# for given n & m has already been executed
if(dp[n][m] != -1):
return dp[n][m]
# If characters are equal, execute
# recursive function for n-1, m-1
if(s1[n - 1] == s2[m - 1]):
if(dp[n - 1][m - 1] == -1):
dp[n][m] = minDis(s1, s2, n - 1, m - 1, dp)
return dp[n][m]
else:
dp[n][m] = dp[n - 1][m - 1]
return dp[n][m]
# If characters are nt equal, we need to
# find the minimum cost out of all 3 operations.
else:
if(dp[n - 1][m] != -1):
m1 = dp[n - 1][m]
else:
m1 = minDis(s1, s2, n - 1, m, dp)
if(dp[n][m - 1] != -1):
m2 = dp[n][m - 1]
else:
m2 = minDis(s1, s2, n, m - 1, dp)
if(dp[n - 1][m - 1] != -1):
m3 = dp[n - 1][m - 1]
else:
m3 = minDis(s1, s2, n - 1, m - 1, dp)
dp[n][m] = 1 + min(m1, min(m2, m3))
return dp[n][m]
# Driver code
str1 = "GEEXSFRGEEKKS"
str2 = "w3wiki"
n = len(str1)
m = len(str2)
dp = [[-1 for i in range(m + 1)] for j in range(n + 1)]
print(minDis(str1, str2, n, m, dp))
using System;
using System.Collections.Generic;
class GFG {
static int minDis(string s1, string s2, int n, int m,
List<List<int> > dp)
{
// If any string is empty,
// return the remaining characters of other string
if (n == 0)
return m;
if (m == 0)
return n;
// To check if the recursive tree
// for given n & m has already been executed
if (dp[n][m] != -1)
return dp[n][m];
// If characters are equal, execute
// recursive function for n-1, m-1
if (s1[n - 1] == s2[m - 1]) {
if (dp[n - 1][m - 1] == -1) {
return dp[n][m]
= minDis(s1, s2, n - 1, m - 1, dp);
}
else
return dp[n][m] = dp[n - 1][m - 1];
}
// If characters are nt equal, we need to
// find the minimum cost out of all 3 operations.
else {
int m1, m2, m3; // temp variables
if (dp[n - 1][m] != -1) {
m1 = dp[n - 1][m];
}
else {
m1 = minDis(s1, s2, n - 1, m, dp);
}
if (dp[n][m - 1] != -1) {
m2 = dp[n][m - 1];
}
else {
m2 = minDis(s1, s2, n, m - 1, dp);
}
if (dp[n - 1][m - 1] != -1) {
m3 = dp[n - 1][m - 1];
}
else {
m3 = minDis(s1, s2, n - 1, m - 1, dp);
}
return dp[n][m]
= 1 + Math.Min(m1, Math.Min(m2, m3));
}
}
// Driver code
static void Main()
{
string str1 = "GEEXSFRGEEKKS";
string str2 = "w3wiki";
int n = str1.Length, m = str2.Length;
List<List<int> > dp = new List<List<int> >();
for (int i = 0; i < n + 1; i++) {
dp.Add(new List<int>());
for (int j = 0; j < m + 1; j++) {
dp[i].Add(-1);
}
}
Console.WriteLine(minDis(str1, str2, n, m, dp));
}
}
function minDis(s1,s2,n,m,dp)
{
// If any String is empty,
// return the remaining characters of other String
if(n == 0)
return m;
if(m == 0)
return n;
// To check if the recursive tree
// for given n & m has already been executed
if(dp[n][m] != -1)
return dp[n][m];
// If characters are equal, execute
// recursive function for n-1, m-1
if(s1[n - 1] == s2[m - 1])
{
if(dp[n - 1][m - 1] == -1)
{
return dp[n][m] = minDis(s1, s2, n - 1, m - 1, dp);
}
else
return dp[n][m] = dp[n - 1][m - 1];
}
// If characters are nt equal, we need to
// find the minimum cost out of all 3 operations.
else
{
let m1, m2, m3; // temp variables
if(dp[n-1][m] != -1)
{
m1 = dp[n - 1][m];
}
else
{
m1 = minDis(s1, s2, n - 1, m, dp);
}
if(dp[n][m - 1] != -1)
{
m2 = dp[n][m - 1];
}
else
{
m2 = minDis(s1, s2, n, m - 1, dp);
}
if(dp[n - 1][m - 1] != -1)
{
m3 = dp[n - 1][m - 1];
}
else
{
m3 = minDis(s1, s2, n - 1, m - 1, dp);
}
return dp[n][m] = 1 + Math.min(m1, Math.min(m2, m3));
}
}
// Driver program
let str1 = "GEEXSFRGEEKKS";
let str2 = "w3wiki";
let n= str1.length, m = str2.length;
let dp = new Array(n + 1);
for(let i = 0; i < n + 1; i++)
{
dp[i]=new Array(m+1);
for(let j=0;j<m+1;j++)
dp[i][j]=-1;
}
console.log(minDis(str1, str2, n, m, dp));
Output
3
Time Complexity: O(m x n)
Auxiliary Space: O( m *n)+O(m+n) , (m*n) extra array space and (m+n) recursive stack space.
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