Edit Distance LeetCode Solution

Difficulty Level Hard
Frequently asked in Amazon Apple Bloomberg Cisco Facebook Google LinkedIn Microsoft Samsung Uber Yahoo
RubirkViews 2901

Problem Statement

The problem Edit Distance LeetCode Solution states that you are given two strings word1 and word2 and you need to convert word1 into word2 in minimum operations. The operations that can be performed on the string are –

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

Examples

Test Case 1 –

Input: word1 – horse word2 – ros

Output: 3

Explanation:

horse -> rorse (replace ‘h’ with ‘r’)

rorse -> rose (remove ‘r’)

rose -> ros (remove ‘e’)

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

Approach

Recursive Approach

  1. We need to traverse both the strings letter by letter either from left or right. Suppose we start from the right corner.
  2. Suppose n is the length of word1 and m is the length of word2.
  3. Consider the last characters of the two strings. Following two cases can arise for these characters –
    1. If the last characters are the same, we can ignore these characters and recur for the rest of the strings i.e. recur for lengths (n-1) and (m-1).
    2. If the last two characters do not match, then we can use one of the three mentioned operations and take the minimum of the three, plus one for the current operation, as the answer. The three operations will be
      • Insert – Recur for lengths n and (m-1)
      • Delete – Recur for lengths (n-1) and m
      • Replace – Recur for lengths (n-1) and (m-1)

DP Approach

Clearly, the recursive approach is not an efficient one as in the worst case, the time complexity for the approach will be exponential. If you draw the recursion tree for some input, you will notice that there are several overlapping subproblems and a DP-based approach can be thought of for the problem. So we need to convert the recursive solution to a DP-based solution by storing the computed results in a temporary data structure.

Edit Distance LeetCode Solution

  1. Let n be the length of the first string and m be the length of the second word. We will create a DP matrix of size (n+1)*(m+1) to store the results.
  2. Element dp[i][j] will represent the minimum number of operations required to make the substring word1[0....i) equal to the substring word2[0....j].
  3. The first row of the matrix will represent the input when word1 is an empty string and the first column of the matrix will represent the input when word2 is an empty string. So the base cases will be dp[i][0] = i for i in the range (0,n+1) and dp[0][j] = j for j in the range (0,m+1).
  4. Once the base cases are initialized, we can compute the rest of the elements in a way similar to the recursive approach.
    1. If the (i-1)th character of word1 matches (j-1)th character of word2, dp[i][j] = dp[i-1][j-1].
    2. Else we will apply one of the following operations and take minimum of the three
      • Insert – dp[i][j-1] + 1
      • Delete – dp[i-1][j] + 1
      • Replace – dp[i-1][j-1] + 1
  5. Finally, we can return the value of dp[n][m].

Code for Edit Distance LeetCode Solution

C++

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        int ans = 0;
        vector<vector<int>> dp(n+1, vector<int>(m+1));
        for(int i=0;i<=n;i++) dp[i][0] = i;
        for(int i=0;i<=m;i++) dp[0][i] = i;
        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 dp[i][j] = 1 + min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]));
            }
        }
        return dp[n][m];
    }
};

JAVA

class Solution {
    public int min(int a, int b, int c){
        if(a<=b && a<=c) return a;
        if(b<=a && b<=c) return b;
        return c;
    }
    public int minDistance(String word1, String word2) {
        int n = word1.length(), m = word2.length();
        char first[] = word1.toCharArray();
        char second[] = word2.toCharArray();
        int dp[][] = new int[n+1][m+1];
        for(int i=0;i<=n;i++) dp[i][0] = i;
        for(int i=0;i<=m;i++) dp[0][i] = i;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(first[i-1] == second[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];
    }
}

Python

class Solution(object):
    def minDistance(self, word1, word2):
        n = len(word1)+1
        m = len(word2)+1
        dp = [[0 for i in range(m)] for j in range(n)]
        
        for i in range(0,n):
            dp[i][0] = i
        
        for j in range(0,m):
            dp[0][j] = j
        
        for i in range(1,n):
            for j in range(1,m):
                if word1[i-1] == word2[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])
        
        # print(dp)
        return dp[n-1][m-1]

Complexity Analysis for Edit Distance LeetCode Solution

Time Complexity

We are traversing through a matrix of size n*m where n and m are lengths of the two strings. So the overall complexity for the algorithm is O(n*m).

Space Complexity

We are creating a matrix of size n*m where n and m are lengths of the two strings to store the result for the sub-problems. So the space complexity for the algorithm is O(n*m).

Reference: https://en.wikipedia.org/wiki/Dynamic_programming

Translate »