Leetcode 72. Edit Distance

Problem Link : https://leetcode.com/problems/edit-distance/

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

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

Solution:

Edit distance between two strings is the minimum number of operations required to convert one string to another. We are given two strings word1 and word2 and are asked to calculate minimum number of operations(insert, delete or replace) required to convert word1 to word2.

Let's try to solve this problem recursively with caching/ top down

class Solution {
public:
    
    // Stores precomputed (i, j) i,e cost for s with length i and
    // t with j length
    map<pair<int, int>, int> mp;
    
    string s, t;
    int helper(int i, int j){
        
        // If already computed for length i and j simply return computed value
        if (mp.find({i, j}) != mp.end()){
            return mp[{i, j}];
        }
        
        // If length of the first string is 0
        // Then we need to insert all the characters equal to length of 
        // second string
        // eg: s = "" and t = "ram"
        // Then we need to insert 3 characters "ram" into s
        
        if(i == 0){
            return j;
        }
        
        // If length of second string is 0
        // Then we need to delete 3 characters from first string
        if(j == 0){
            return i;
        }
        
        // If the corresponding ith and jth character matches 
        // we don't need any operations
        // we just solve for (i - 1) length and (j - 1) length of s and t
        // eg: s = "ram" and t = "cram"
        // Here s[2] == t[3]. So we dont need any additional operation
        // We just solve for its smaller instance i.e s becomes "ra" and t becomes "cra"
        if(s[i - 1] == t[j - 1]){
            return helper(i - 1, j - 1);
        }
        
        // Insert 
        // s = "horse", t = "ros"
        // We insert character 's' costing 1 operations
        // "horses" and "ros" i.e we can eliminate matcging characters from last
        // Then problem reduces to "horse" and "ro"
        // i.e length of string s doesn't change but string t reduces by size 1
        int ins = 1 + helper(i , j - 1);
        
        // Replace
        // eg: = "horse", t = "ros"
        // We can replace last character of string s to 's' with 1 cost operation
        // Then we can eliminate matching characters
        // Then problem reduces to "hors" and "ro"
        // i.e length of s reduces by 1 and t reduces by 1
        int rep = 1 + helper(i - 1, j - 1);
        
        // Delete
        // eg: "horse", t = "ros"
        // We can delete last character from string s with cost 1
        // Then problem reduces to "hors" and "ros"
        // i.e length of s reduces by 1 but length of t doesnt change
        int del = 1 + helper(i - 1, j);
        
        // Save the computed result in dictionary
        mp[{i, j}] = min({ins, rep, del});
        return mp[{i, j}];
        
    }
    int minDistance(string word1, string word2) {
       s = word1;
       t = word2;
       return helper(word1.size(), word2.size());
    }
};

Top-Down approach passes the testcases but sometimes may cause stack overhead due to more recursive calls and you may face issues in language like python unless you explicitly set recursion limit.
So let's try translating the code to bottom up dp.
The first thing we can observe is we are interested only in two parameters :

• length of word1 (i)
• length of word2 (j)

We can write f(i, j) as dp[i][j] which stores edit distance between two string word1 and word2

Translating the code is straight forward, just replace the function call with dp array states. See the implementation

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