• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Leetcode: Edit Distance

October 10, 2019 by Arshdeep Singh

Given two words word1 and word2, find the edit distance between word1 and word2 i.e. 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

Example 1:

Input: word1 = “horse”, word2 = “ros”
Output: 3
Explanation:
horse -> rorse (replace ‘h’ with ‘r’)
rorse -> rose (remove ‘r’)
rose -> ros (remove ‘e’)

Example 2:

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’)

Constrains:

1 <= ( |word1| * |word2| ) <= 10^6

Question Link: Edit Distance

Solution: 

This problem looks like a typical usecase of recursion to in which we have three cases:

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

The way to approach these kinds of recursive problems is to assume that the all the previous characters have been fixed and the current state is what we are going to fix ( here we have to make the current state character equal). Here we can fix the current state in these three ways:

Insert a character:
When we are at a state of one less character in one word than the other, then insertion of a character can be used such as:

Delete a character:
When we are at a state of one less character in one word than the other, then deletion of a character can be used such as:

Replace a character:
When we are at a state of both words being same except the current state’s characters are different then replacing a character can be used such as:

But here is the main part, we don’t need to replace a character if the character at the current both states are same.

Terminating Condition:
When one of our current state reaches the end of its word, then we have to terminate by adding the inserting the remaining characters of the other word at the end of this word.

Switching Rule:
So when we are switching from one state to the next state, we need to check: If the current states have same character?

If YES, then directly go to the next state without performing any operation.

Otherwise, answer will be min (operation1, operation2, operation3) + 1.

Code:

Implemented in C++

class Solution {
public:
    // Helper fuction to calculate the answer
    int rec(string &word1, string &word2, int i, int j){

        // Base Cases where current state reaches its end
        if (i == word1.length()) return word2.length() - j;
        if (j == word2.length()) return word1.length() - i;
        
        // Checking if word is same, then directly pass
        if(word1[i] == word2[j]) return rec(word1, word2, i+1, j+1);

        // different, so taking minimum of all three
        return min( min(rec(word1, word2, i+1, j), rec(word1, word2, i, j+1)), rec(word1, word2, i+1, j+1)) + 1;
    }
    
    int minDistance(string word1, string word2) {
        //Recursive solution
        return rec(word1, word2, 0, 0);
    }
};

But the worst case complexity of this solution is 3^max(|word1|, |word2|)

Optimization:

The optimization that we require here is to use Dynamic Programming inplace of Recursion.

The difference would be how to define base cases:
Here bases cases would be when current state contains zero words of one the word. In such a case, the dp value (minimum number of oper) for that state would be length of the other word (by consecutive addition operations).

We can either use Memoization or Bottom Up approach. Here we have implemented the bottom up approach:

To understand a Bottom Up DP approach the following table can be used:

2-D DP Table
2-D DP Table

Here base conditions are used to fill first row and first column.
For the rest, we can use the Recursive Equation:

DP[i][j] :
if word1[i] == word2[j] : dp[i-1][j-1]
else : min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

After filling the table would look like:

2-D DP Table Filled
2-D DP Table Filled

CODE:

Implemented in C++

class Solution {
public:
    int minDistance(string word1, string word2) {
        // DP Solution
        int n1 = word1.length(); //length of word1
        int n2 = word2.length(); //length of word2
        // declaring a dp double dimension array
        // dp[i][j] = min num of opers to perform to make
        // word1 upto length i and word2 upto length j equal
        int dp[n1+1][n2+1];

        //base conditions as discussed above
        for(int i=0;i<=n1;i++) dp[i][0] = i;
        for(int i=0;i<=n2;i++) dp[0][i] = i;
        
        // looping through all cases
        for(int i=1;i<=n1;i++){
            for(int j=1;j<=n2;j++){
                if(word1[i-1]==word2[j-1]) //when current state contains same characters
                    dp[i][j] = dp[i-1][j-1];
                else //different, so minimum of all three opers with +1
                    dp[i][j] = min( min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
            }
        }
        
        return dp[n1][n2]; //min opers to make word1 equal to word2 or vice versa
    }
};

Here the time complexity would be O( |word1| * |word2| ) and space complexity would also be O( |word1| * |word2| ) .

Similar Articles

Filed Under: Algorithm, Amazon Interview Question, Google, LeetCode, Uncategorized Tagged With: Dynamic Programming, Recursion, string

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Maximum size of square sub matrix with all 1’s in a binary matrix

Calculate price of parking from parking start end time prices

Flipkart Set 1 On Campus with Answers

Circular Linked List

Apriori algorithm C Code Data Mining

Generate next palindrome number

VMWare SDEII Interview

Find loop in Singly linked list

VMWare Openings

Get K Max and Delete K Max in stream of incoming integers

Max Sum in circularly situated Values

DFS (Depth First Search)

HackeEarth Flipkart’s Drone

Regular Expression Matching

Given a sorted array and a number x, find the pair in array whose sum is closest to x

Advanced SQL Injection

Find the kth number with prime factors 3, 5 and 7

Python String and numbers

N Petrol bunks or City arranged in circle. You have Fuel and distance between petrol bunks. Is it possible to find starting point so that we can travel all Petrol Bunks

Check if an array has duplicate numbers in O(n) time and O(1) space

ADOBE Aptitude C Language Test

Given a float number convert it into the string WITHOUT using any inbuilt Function

Puzzle : 100 doors in a row Visit and Toggle the door. What state the door will be after nth pass ?

Word Break Problem

Generate largest number arranging a no. of given non negative integer numbers

Find Nearest Minimum number in left side in O(n)

The Magic HackerEarth Nirvana solutions Hiring Challenge

Naurki.com Security Breach

Fibonacci Hashing & Fastest Hashtable

Length of the longest substring without repeating characters

Copyright © 2025 · Genesis Framework · WordPress · Log in