Edit Distance

Companies:
  • Amazon Interview Questions
  • ByteDance Interview Questions
  • Facebook Interview Questions
  • Google Interview Questions
  • Uber Interview Questions

Problem Statement

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

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

Sample Test Cases

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

Problem Solution

We will be using Dynamic Programming Bottom-up approach.

We can maintain a DP table. Since, it is a bottom-up approach where do[I][j] gives you the minimum number of changes required when word1 is of size I and word2 is of size j.
So our answer will be dp[n][m] since word1 is of size n and word2 is of size m.

Now the base case is when any of word1 or word2 is empty. Then the answer is the length of word1 or word2 whichever is not empty.

Now after handling the base case we fill the DP table by using the three options (insert, delete or replace, any one of which will cost us 1 point). So we fill the dp by using the minimum of these three (insert, delete or replace points).

Now you have to figure out that
If:
word1[pos] = word2[pos], we have to add nothing to our answer
Else:
dp[i – 1][j – 1] is for replace,
dp[i – 1][j] is for delete,
dp[i][j – 1] is for insert.
and add 1 + min of the above three cases to our answer.

Complexity Analysis

Time Complexity: O( nm ) because we are traversing the matrix of size m x n (where m and n are the length of the strings).

Space Complexity: O( nm ) because we have to maintain the dp matrix of size m x n (where m and n are the length of the strings).

Code Implementation

#include<bits/stdc++.h>
using namespace std;

int minDistance(string word1, string word2) {
        int n = word1.size(), m = word2.size();

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

        // if word2 is empty we have to remove all characters from word1
        for(int i = 0; i <= n; i++) dp[i][0] = i;

        // if word1 is empty we have to add all characters to word1
        for(int j = 0; j <= m; j++) dp[0][j] = j;

        // we have three cases replace, delete, insert
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 1 + min(replace, delete, insert)
                    dp[i][j] = 1 + min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1]));
                }
            }
        }
        return dp[n][m];
    }
int main()
{
    string a="horse";
    string b="ros";

    int x= minDistance(a,b);
    cout<<x;
}

 

Scroll to Top

Full Stack Integrated Bootcamp Free Trial

  • Please enter a number from 7000000000 to 9999999999.