Edit Distance

You can either replace, insert or delete. return minimum operation to convert str1 to str2

Edit Distance

Problem

You are given two strings, word1 and word2. Return the minimum number of operations needed to convert word1 into word2.

You can use only these three operations:

• Insert a character
• Delete a character
• Replace a character

Examples

Example 1

Input: word1 = "horse", word2 = "ros"
Output: 3

• horse -> rorse (replace h with r)
• rorse -> rose (remove r)
• rose -> ros (remove e)

Example 2

Input: word1 = "intention", word2 = "execution"
Output: 5

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

Constraints

• 0 <= word1.length, word2.length <= 500
• word1 and word2 contain only lowercase English letters.

Main Idea

We compare the last characters of both strings. Let i point to the end of word1 and j point to the end of word2.

• If the characters match, we do not need any operation. We move one step back in both strings.
• If the characters do not match, we try all three operations and take the smallest result. We add 1 for the operation we use.

Here is what each operation means:

• Insert: add the matching character to word1. We move back in word2 only. This is (i, j - 1).
• Delete: remove the character from word1. We move back in word1 only. This is (i - 1, j).
• Replace: change the character in word1. We move back in both strings. This is (i - 1, j - 1).

Base Cases

• If word1 is finished, we must insert all the remaining characters of word2.
• If word2 is finished, we must delete all the remaining characters of word1.

Solution 1: Recursion + Memoization (0-Based Index)

We write a recursive function and save each answer in a table. So we never solve the same problem twice.

Here, i and j are 0-based indexes. When a string is finished, the index becomes -1. So the number of remaining characters is j + 1 or i + 1.

var minDistance = function (word1, word2) {
    let n = word1.length;
    let m = word2.length;
    let dp = Array.from({ length: n }, () => Array(m));

    function recurr(i, j) {
        // word1 is finished, insert the rest of word2
        if (i < 0) {
            return j + 1;
        }

        // word2 is finished, delete the rest of word1
        if (j < 0) {
            return i + 1;
        }

        // answer is already saved
        if (dp[i][j] !== undefined) {
            return dp[i][j];
        }

        if (word1[i] === word2[j]) {
            // characters match, no operation needed
            dp[i][j] = recurr(i - 1, j - 1);
        } else {
            // try insert, delete and replace
            dp[i][j] =
                1 +
                Math.min(
                    recurr(i, j - 1),     // insert
                    recurr(i - 1, j),     // delete
                    recurr(i - 1, j - 1)  // replace
                );
        }

        return dp[i][j];
    }

    return recurr(n - 1, m - 1);
};

Complexity

• Time Complexity: O(n * m)
  • n is the length of word1 and m is the length of word2.
  • There are n * m different states, and each state is solved only once.
• Space Complexity: O(n * m)
  • The dp table stores n * m values.
  • The recursion stack uses O(n + m) extra space.

Solution 2: Memoization (1-Based Index)

In a table, we cannot use a negative index like -1. So we shift everything by one step and use 1-based indexing.

• i now means "the first i characters of word1".
• j now means "the first j characters of word2".
• The base cases become i == 0 and j == 0.
• We compare word1[i - 1] and word2[j - 1], because strings still start from index 0.

This version is easier to change into tabulation.

var minDistance = function (word1, word2) {
    let n = word1.length;
    let m = word2.length;
    let dp = Array.from({ length: n + 1 }, () => Array(m + 1));

    function recurr(i, j) {
        // word1 is empty, insert j characters
        if (i === 0) {
            return j;
        }

        // word2 is empty, delete i characters
        if (j === 0) {
            return i;
        }

        // answer is already saved
        if (dp[i][j] !== undefined) {
            return dp[i][j];
        }

        if (word1[i - 1] === word2[j - 1]) {
            // characters match, no operation needed
            dp[i][j] = recurr(i - 1, j - 1);
        } else {
            // try insert, delete and replace
            dp[i][j] =
                1 +
                Math.min(
                    recurr(i, j - 1),     // insert
                    recurr(i - 1, j),     // delete
                    recurr(i - 1, j - 1)  // replace
                );
        }

        return dp[i][j];
    }

    return recurr(n, m);
};

Complexity

• Time Complexity: O(n * m)
  • Each of the (n + 1) * (m + 1) states is solved only once.
• Space Complexity: O(n * m)
  • The dp table has (n + 1) * (m + 1) cells.
  • The recursion stack uses O(n + m) extra space.

Solution 3: Tabulation (Bottom-Up)

In this method, we do not use recursion. We fill the table step by step, starting from the smallest problem.

Here, dp[i][j] means: the minimum number of operations to convert the first i characters of word1 into the first j characters of word2.

var minDistance = function (word1, word2) {
    let n = word1.length;
    let m = word2.length;
    let dp = Array.from({ length: n + 1 }, () => Array(m + 1).fill(0));

    // word2 is empty, delete all i characters
    for (let i = 0; i <= n; i++) {
        dp[i][0] = i;
    }

    // word1 is empty, insert all j characters
    for (let j = 0; j <= m; j++) {
        dp[0][j] = j;
    }

    // Fill the table
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            if (word1[i - 1] === word2[j - 1]) {
                // characters match, no operation needed
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                // try insert, delete and replace
                dp[i][j] =
                    1 +
                    Math.min(
                        dp[i][j - 1],     // insert
                        dp[i - 1][j],     // delete
                        dp[i - 1][j - 1]  // replace
                    );
            }
        }
    }

    return dp[n][m];
};

Complexity

• Time Complexity: O(n * m)
  • We use two loops, one inside the other.
  • Each cell is filled in constant time.
• Space Complexity: O(n * m)
  • The dp table has (n + 1) * (m + 1) cells.
  • There is no recursion stack.

Comparison

Summary

• This is a classic dynamic programming problem.
• If the last characters match, we copy the answer from the diagonal cell.
• If they do not match, we take the minimum of insert, delete and replace, and add 1.
• 1-based indexing helps us avoid negative indexes, so the code is easy to change into tabulation.
• All solutions run in O(n * m) time.
• Tabulation avoids recursion, so it is safer for long strings.