# 72. 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:

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

Approach 1: DP in 2D. Space can be optimized to be O(N) instead of O(MN) where M and N are lengths of the words.

# Code (Python)

Approach 1:

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        # table[j][i] -- edit distance between word1[:j] and word2[:i]
        table = [[float('inf') for _ in range(len(word2) + 1)] for _ in range(len(word1) + 1)]
        table[0][0] = 0
        for i in range(1, len(word2) + 1):
            table[0][i] = i
        for j in range(1, len(word1) + 1):
            table[j][0] = j
            for i in range(1, len(word2) + 1):
                if word1[j-1] == word2[i-1]:
                    table[j][i] = table[j-1][i-1]
                else:
                    table[j][i] = min(table[j-1][i-1], table[j][i-1], table[j-1][i]) + 1
        return table[-1][-1]

    def minDistance(self, word1: str, word2: str) -> int:
        # space optimization: O(N) instead of O(MN) where M and N are lengths
        table = [i for i in range(len(word2) + 1)]
        for j in range(1, len(word1) + 1):
            table_prev_val = table[0]
            table[0] = j
            for i in range(1, len(word2) + 1):
                if word1[j-1] == word2[i-1]:
                    table_j_i = table_prev_val
                else:
                    table_j_i = min(table_prev_val, table[i-1], table[i]) + 1
                table_prev_val = table[i]
                table[i] = table_j_i
        return table[-1]

# Code (C++)

Approach 1:

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n1 = word1.size();
        int n2 = word2.size();
        int ops[n1+1][n2+1];
        ops[0][0] = 0;
        for (int i = 1; i <= n1; ++i)
            ops[i][0] = i;
        for (int i = 1; i <= n2; ++i)
            ops[0][i] = i;
        for (int i = 1; i <= n1; ++i)
        {
            for (int j = 1; j <= n2; ++j)
            {
                ops[i][j] = std::min(ops[i-1][j] + 1,
                    std::min(ops[i][j-1] + 1,
                        ops[i-1][j-1] + ((word1[i-1] == word2[j-1]) ? 0 : 1)));
            }
        }
        return ops[n1][n2];
    }
};

// Space can be optimized to be O(N) instead of O(MN) where M and N are lengths of the words.
class Solution {
public:
    int minDistance(string word1, string word2) {
        int n1 = word1.size();
        int n2 = word2.size();
        int prev[n2+1];
        for (int len2 = 0; len2 <= n2; ++len2)
            prev[len2] = len2;
        for (int len1 = 1; len1 <= n1; ++len1)
        {
            int tmp = prev[0];
            prev[0] = len1;
            for (int len2 = 1; len2 <= n2; ++len2)
            {
                int curr = std::min(prev[len2-1] + 1,
                    std::min(prev[len2] + 1,
                        tmp + ((word1[len1-1] == word2[len2-1]) ? 0 : 1)));
                tmp = prev[len2];
                prev[len2] = curr;
            }
        }
        return prev[n2];
    }
};