46. Edit Distance

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

• Insert a character

• Delete a character

• 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: (Recursion)

Approach

1. If last characters of two strings are same, nothing much to do. Ignore last characters and get count for remaining strings. So we recur for lengths m-1 and n-1.

2. Else (If last characters are not same), we consider all operations on ‘str1’, consider all three operations on last character of first string, recursively compute minimum cost for all three operations and take minimum of three values.

   1. Insert: Recur for m and n-1

   2. Remove: Recur for m-1 and n

   3. Replace: Recur for m-1 and n-1

class Solution
{
public:
    int editDistance(string s1, string s2, int n, int m)
    {

        if (n == 0)
        {
            return m;
        }

        if (m == 0)
        {
            return n;
        }

        if (s1[n-1] == s2[m-1])
        {
            return editDistance(s1, s2, n - 1, m - 1);
        }
        else
        {
            return 1 + min(min(editDistance(s1, s2, n, m - 1), editDistance(s1, s2, n - 1, m)), editDistance(s1, s2, n - 1, m - 1));
        }
    }
    
    int minDistance(string word1, string word2)
    {

        int n = word1.length();
        int m = word2.length();
        return editDistance(word1, word2, n, m);
    }
};

Time Complexity: O(3^n) exponential

Solution: (DP)

class Solution
{
public:
    int minDistance(string s1, string s2)
    {

        int n = s1.length();
        int m = s2.length();

        if (n == 0)
        {
            return m;
        }

        if (m == 0)
        {
            return n;
        }

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

        for (int i = 0; i <= n; i++)
        {
            v[i][0] = i;
        }

        for (int j = 0; j <= m; j++)
        {
            v[0][j] = j;
        }

        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (s1[i - 1] == s2[j - 1])
                {
                    v[i][j] = v[i - 1][j - 1];
                }
                else
                {
                    v[i][j] = min(min(1 + v[i][j - 1], 1 + v[i - 1][j]), 1 + v[i - 1][j - 1]);
                }
            }
        }

        return v[n][m];
    }
};

Time Complexity: O(n * m) Space Complexity: O(n * m)