Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Problem

Submissions

Hints & solutions

Discuss

Edit Distance

Moderate

0/80

Average time to solve is 30m

Contributed by

149 upvotes

Asked in companies

Problem statement

You are given two strings 'S' and 'T' of lengths 'N' and 'M' respectively. Find the "Edit Distance" between the strings.

Edit Distance of two strings is the minimum number of steps required to make one string equal to the other. In order to do so, you can perform the following three operations:

1. Delete a character
2. Replace a character with another one
3. Insert a character

Note:

Strings don't contain spaces in between.

Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line of input contains the string 'S' of length 'N'.

The second line of the input contains the String 'T' of length 'M'.

Output format:

The only line of output prints the minimum "Edit Distance" between the strings.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given functions.

Constraints:

0 <= N <= 10 ^ 3
0 <= M <= 10 ^ 3

Time Limit : 1sec

Sample Input 1 :

abc
dc

Sample Output 1 :

Explanation For Sample Input 1 :

In 2 operations we can make the string T to look like string S. First, insert the character 'a' to string T, which makes it "adc".

And secondly, replace the character 'd' of the string T with 'b' from the string S. This would make string T to "abc" which is also the string S. Hence, the minimum distance.

Sample Input 2 :

whgtdwhgtdg
aswcfg

Sample Output 2 :

Hint 1

Hint 2

Hint 3

Try to think of a recursive approach and formulate the recurrence relation. Try performing the operations as required.

Approaches (3)

Approach 1

Approach 2

Approach 3

Recursive Approach

We will write a recursive approach.
The base case would be if the length of the first string is 0 then we need to add all the characters of the second string to the first string hence return the length of the second string. Similarly, if the length of the second string is 0 return length of the first string.
Now the recurrence relation is as follows:
- If the last characters of two strings are not the same, try all operations and it will cost 1. Here i is initially the last index of s1 and j is initially the last index of s2 and f(i, j) is the edit distance of str1(0, i) to str2(0, j). str(i, j) denotes the substring formed by taking the characters at index i through index j.
- f(i, j) = 1 + min(f(i - 1, j), f(i, j - 1), f(i - 1, j - 1))
- Here the three recursive calls are for the insert, remove and replace respectively and s1, s2 will be parameters of all function calls. If the last characters of two strings are the same (s1[i] == s2[j]) then the relationship would be:
  - f(i, j) = f(i - 1, j - 1)

Time Complexity

O(3 ^ (N * M)), Where N is the size of the first string and M is the size of the second string.

Since we are making 3 recursive calls each time, therefore the time complexity is O(3 ^ (N * M)).

Space Complexity

O(N + M), Where N is the size of the first string and M is the size of the second string.

Since we are making recursive calls that require the recursion stack. Therefore the space complexity is O(N + M).

(75% EXP penalty)

(100% EXP penalty)

Edit Distance

Shivam Jha

Interview problems

EASY DP TABULATION ✅✅✅

#include <bits/stdc++.h>

int editDistance(string str1, string str2) {

int n = str1.size();

int m = str2.size();

vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

for (int i = 0; i <= n; i++)

dp[i][0] = i;

for (int j = 0; j <= m; j++)

dp[0][j] = j;

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= m; j++) {

if (str1[i - 1] == str2[j - 1]) {

dp[i][j] = dp[i - 1][j - 1];

} else {

int val1 = 1 + dp[i - 1][j];

int val2 = 1 + dp[i][j - 1];

int val3 = 1 + dp[i - 1][j - 1];

dp[i][j] = min(val1, min(val2,val3));

}

return dp[n][m];

}

37 views

0 replies

1 upvote

MANOJ S B

Interview problems

JAVA-DP-TABULATION

public class Solution {

public static int editDistance(String s1, String s2) {

int n=s1.length();

int m=s2.length();

int[][] dp=new int[n+1][m+1];

for(int i=0;i<=n;i++)

{

for(int j=0;j<=m;j++)

{

if(j==0)

{

dp[i][j]=i;

}else if(i==0)

{

dp[i][j]=j;

}else if(s1.charAt(i-1)==s2.charAt(j-1))

{

dp[i][j]=dp[i-1][j-1];

}else

{

dp[i][j]=1+Math.min(dp[i][j-1],Math.min(dp[i-1][j],dp[i-1][j-1]));

}

return dp[n][m];

}

java

31 views

0 replies

0 upvotes

Pratham Ashok Asrani

Interview problems

cpp

#include <bits/stdc++.h>

int editDistance(string s, string t)

{

int n, m;

vector<vector<int>> dp;

n = s.size(), m = t.size();

dp.resize(n+1, vector<int>(m+1, 0));

for(int i = 1; i <= n; i++) dp[i][0] = i;

for(int i = 1; i <= m; i++) dp[0][i] = i;

for(int i = 1; i <= n; i++) {

for(int j = 1; j <= m; j++) {

if(s[i-1] == t[j-1]) {

dp[i][j] = dp[i-1][j-1];

}else{

dp[i][j] = 1+min({dp[i-1][j-1], dp[i-1][j], dp[i][j-1]});

}

return dp[n][m];

}

114 views

0 replies

0 upvotes

Riya

Interview problems

Edit distance tabulation || DP || Explained easy

This question can be easily solved by tabulation also

just follow these steps

first of all create a dp array

dp[n][m]

then do what for dp[0][i] (i variable) just do dp[0][i]=i

then same for the reversed dp[i][0]= i

your first row and column is done hurray!!!!!

after that follow the equation

VERY EASY

first of all tale 2 loops starting from 1 as 0 is already filled for dp

now fill the dp table

if str1[i]==str2[j] then do what

copy the dp[i-1][j-1]

or else take the 1+ min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])

return dp[n][m]

solved

Happy coding!!!!

61 views

0 replies

1 upvote

Vikesh Kumar

Interview problems

C++ || DP || Recursive || Memoisation || Tabulation || Space Optimisation

Recursion

int solve(string &str1, string &str2,int i,int j){
    int n1=str1.size(), n2=str2.size();

    if(i>=n1) return n2-j;
    if(j>=n2) return n1-i;
    
    int ans=0;

    if(str1[i] == str2[j]){
        ans = solve(str1, str2, i+1, j+1);
    }else{
        int Insert =1+solve(str1, str2, i, j+1);
        int Delete =1+solve(str1, str2, i+1, j);
        int Replace =1+solve(str1, str2, i+1, j+1);

        ans =min(Delete, min(Insert,Replace) );
    }
    return ans;
}
int editDistance(string str1, string str2)
{
    //write you code here
    return solve(str1, str2,0,0);
}

Memoisation

int solve1(string &str1, string &str2,int i,int j,vector<vector<int> >&dp){
    int n1=str1.size(), n2=str2.size();

    if(i>=n1) return n2-j;
    if(j>=n2) return n1-i;
    
    if(dp[i][j] != -1){
        return dp[i][j];
    }
    int ans=0;
    
    if(str1[i] == str2[j]){
        ans= solve1(str1, str2, i+1, j+1,dp);
    }else{
        int Insert =1+solve1(str1, str2, i, j+1,dp);
        int Delete =1+solve1(str1, str2, i+1, j,dp);
        int Replace =1+solve1(str1, str2, i+1, j+1,dp);

        ans =min(Delete, min(Insert,Replace) );
    }
    return dp[i][j] =ans;
}
int editDistance(string str1, string str2)
{
    //write you code here
    vector<vector<int> >dp( str1.size(), vector<int>(str2.size(),-1) );
    return solve1(str1,str2,0,0,dp);
}

Tabulation

int solve2(string &str1, string &str2){
    vector<vector<int> >dp(str1.size()+1, vector<int>(str2.size()+1,0) );
    
    for(int j=0; j<str2.size(); j++){
        dp[str1.size()][j] = str2.size()-j;
    }
    for(int i=0; i<str1.size(); i++){
        dp[i][str2.size()]= str1.size()-i;
    }

    
    for(int i=str1.size()-1; i>=0; i--){
        for(int j=str2.size()-1; j>=0; j--){
            int ans=0;
            if(str1[i] == str2[j]){
                ans= dp[i+1][j+1];
            }else{
                int Insert =1+dp[ i][j+1];
                int Delete =1+dp[ i+1][j];
                int Replace =1+dp[ i+1][j+1];

                ans =min(Delete, min(Insert,Replace) );
            }
            dp[i][j] =ans;
        }
    }
    return dp[0][0];
}
int editDistance(string str1, string str2)
{
    //write you code here
    return solve2(str1, str2);
}

Space Optimisation

int solve3(string &str1, string &str2){
    vector<int>curr(str2.size()+1,0);
    vector<int>next(str2.size()+1,0);

    for(int j=0; j<str2.size(); j++){
        next[j] = str2.size()-j;
    }

    for(int i=str1.size()-1; i>=0; i--){
        for(int j=str2.size()-1; j>=0; j--){
            // imp
            curr[str2.size()] = str1.size()-i;

            int ans=0;
            if(str1[i] == str2[j]){
                ans= next[j+1];
            }else{
                int Insert =1+curr[j+1];
                int Delete =1+next[j];
                int Replace =1+next[j+1];

                ans =min(Delete, min(Insert,Replace) );
            }
            curr[j] =ans;
        }
        next =curr;
    }
    return next[0];
}
int editDistance(string str1, string str2)
{
    //write you code here
    return solve3(str1,str2);
}

169 views

0 replies

0 upvotes

Parjanay Sharma

Interview problems

C++, Both Top Down and Bottoms Up Approach

#include <bits/stdc++.h>
int dp[1001][1001] = {-1};

int change(string str1, string str2, int i, int j){
    // Method 1: Top Down Approach
    // trying to make str2 to str1
    if( (i == str1.size()) && (j == str2.size()) ){
        return dp[i][j] = 0;
    }else if( i == str1.size() ){
        return dp[i][j] = str2.size() - j ;
    } else if( j == str2.size() ){
        return dp[i][j] = str1.size() - i ;
    } else if( dp[i][j] != -1){
        return dp[i][j];
    } else {
        if( str1[i] == str2[j] ){
            return dp[i][j] = change(str1, str2, i+1, j+1);
        }else{
            return dp[i][j] = min( 1+change(str1, str2, i+1, j) , min( 1+change(str1, str2, i+1, j+1) , 1 + change(str1, str2, i, j+1) ) );
        }
    }
}
int editDistance(string str1, string str2)
{
    // Method 1: Top Down Approach
    memset(dp, -1 , sizeof dp);
    int ans = change(str1, str2, 0 , 0);
    return ans;
    // Method 2: Bottoms Up Approach
    int n = str1.length();
    int m = str2.length();
    for( int i = 0; i <= n; i++ ){
        dp[i][0] = i;
    }
    for( int j = 0; j <= m; j++ ){
        dp[0][j] = j;
    }
    for( int i = 1; i <= n; i++ ){
        for( int j =1; j <= m; j++ ){
            if( str1[i-1] == str2[j-1] ){
                dp[i][j] = dp[i-1][j-1];
            }else{
                dp[i][j] = 1+ min( dp[i-1][j] , min( dp[i][j-1] , dp[i-1][j-1] ) );
            }
        }
    }
    return dp[n][m];
}

51 views

0 replies

0 upvotes

Shashwat Sharma

Interview problems

python dp easiest

from sys import stdin

import sys

sys.setrecursionlimit(10**7)

def editDistance(s1, s2) :

dp = [[0]*(len(s2)+1) for i in range(len(s1)+1)]

for i in range(len(s1)+1):

for j in range(len(s2)+1):

if i==0: dp[i][j] = j

if j==0 and i!=0: dp[i][j] = i

for i in range(1,len(s1)+1):

for j in range(1,len(s2)+1):

if s1[i-1] == s2[j-1]:

dp[i][j] = dp[i-1][j-1]

else:

dp[i][j] = min(1+dp[i][j-1],1+dp[i-1][j],1+dp[i-1][j-1])

return dp[len(s1)][len(s2)]

35 views

0 replies

0 upvotes

Aakrit Bhandari

Interview problems

C++ || Moderate Solution || Tabulation

int editDistance(string s1, string s2)

{

//write you code here

int n = s1.length();

int m = s2.length();

vector<vector<int>>dp(n+1,vector<int>(m+1,0));

// return getlength(n-1,m-1,s1,s2,dp);

for(int i =0;i<=n;i++)

{

dp[i][0]=i;

}

for(int j =0;j<=m;j++)

{

dp[0][j]=j;

}

for(int i =1;i<=n;i++)

{

for(int j =1;j<=m;j++)

{

if(s1[i-1]==s2[j-1])dp[i][j] = dp[i-1][j-1];

else dp[i][j]= 1+min(dp[i][j-1],min(dp[i-1][j],dp[i-1][j-1]));

}

return dp[n][m];

}

169 views

1 reply

1 upvote

Ambika Kumar Kewat

Interview problems

Edit Distance || Memoization || Tabulation || Space Optimization

#include <bits/stdc++.h>

int memoHelper(int i,int j,string&s,string&t,vector<vector<int>>&dp){

if(i<0) return j+1;

if(j<0) return i+1;

if(dp[i][j]!=-1) return dp[i][j];

if(s[i]==t[j]){

return dp[i][j]=memoHelper(i-1,j-1,s,t,dp);

}else{

return dp[i][j]=1+min(memoHelper(i-1,j,s,t,dp),

min(memoHelper(i,j-1,s,t,dp),memoHelper(i-1,j-1,s,t,dp)));

}

int editDistance(string s, string t)

{

int n=s.size();

int m=t.size();

// vector<vector<int>>dp(n,vector<int>(m+1,-1));

// return memoHelper(n-1,m-1,s,t,dp);

// vector<vector<int>>dp(n+1,vector<int>(m+1,0));

// for(int j=0;j<=m;j++) dp[0][j]=j;

// for(int i=0;i<=n;i++) dp[i][0]=i;

// for(int i=1;i<=n;i++){

// for(int j=1;j<=m;j++){

// if(s[i-1]==t[j-1]){

// dp[i][j]=dp[i-1][j-1];

// }else{

// dp[i][j]=1+min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]));

// }

// return dp[n][m];

vector<int>prev(m+1,0),cur(m+1,0);

for(int j=0;j<=m;j++) prev[j]=j;

for(int i=1;i<=n;i++){

cur[0]=i;

for(int j=1;j<=m;j++){

if(s[i-1]==t[j-1]){

cur[j]=prev[j-1];

}else{

cur[j]=1+min(prev[j],min(cur[j-1],prev[j-1]));

}

prev=cur;

}

return prev[m];

}

138 views

0 replies

0 upvotes

RAJESH KUMAR YADAV

Interview problems

C++ || Easy To Understand

int solveSO(string& a, string& b) {

vector<int> next(b.length() + 1, 0);

vector<int> curr(b.length() + 1, 0);

for (int j = 0; j <= b.length(); j++) {

next[j] = b.length() - j;

}

for (int i = a.length() - 1; i >= 0; i--) {

curr[b.length()] = a.length() - i;

for (int j = b.length() - 1; j >= 0; j--) {

int ans = 0;

if (a[i] == b[j]) {

ans = next[j + 1];

} else {

// Insert

int insertAns = 1 + curr[j + 1];

// Delete

int deleteAns = 1 + next[j];

// Replace

int replaceAns = 1 + next[j + 1];

ans = min(insertAns, min(deleteAns, replaceAns));

}

curr[j] = ans;

}

next = curr;

}

return next[0];

}

int editDistance(string str1, string str2)

{

//write you code here

if (str1.length() == 0)

{

return str2.length();

}

if (str2.length() == 0) {

return str1.length();

}

return solveSO(str1, str2);

}

58 views

0 replies

0 upvotes

Console