hard

Edit Distance

Find the fewest single-character edits needed to turn one word into another.

1. Define the problem

Edit Distance

Given two strings word1 and word2, return the minimum number of single-character operations required to convert word1 into word2. You may insert, delete, or replace a character. When the current characters match, no operation is needed — carry forward the answer for both strings one character shorter, a smaller subproblem already solved. When they don't match, an operation is unavoidable: try a replace, an insert, and a delete, each pointing at one of three neighboring subproblems , and keep the cheapest.

Constraints

  • 0 ≤ word1.length, word2.length ≤ 500
  • word1 and word2 consist of lowercase English letters

Example

Inputword1 = "horse", word2 = "ros"
Output3

Explanation horse -> rorse (replace h with r) -> rose (delete r) -> ros (delete e), 3 operations.

2. Visualize the solution

Fill one row per character, matching or taking the cheapest edit

Fill one row per character, matching or taking the cheapest edit
Statusrow 0 (empty word1)

word1="ab", word2="ac". Turning empty into "", "a", "ac" costs 0, 1, 2 inserts: row = [0, 1, 2].

What happens in this step

word1 = "ab", word2 = "ac"
dp[0][0] = 0, dp[0][1] = 1, dp[0][2] = 2

Turning the empty string into a prefix of word2 of length j always takes j inserts — this row is the base case.
Step 1 of 3

Steps to visualize

  1. Build a table with an extra empty row and column: dpi[0] = i and dp0[j] = j, since turning an empty string into a string of length k always takes k inserts.
  2. When word1[i-1] equals word2[j-1], dpi[j] = dp[i-1][j-1] — no edit needed.
  3. Otherwise, dpi[j] = 1 + the smallest of the replace, insert, and delete subproblems.
  4. The bottom-right cell holds the minimum number of operations.
3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Fill one row per character, matching or taking the cheapest edit
Statusrow 0 (empty word1)

word1="ab", word2="ac". Turning empty into "", "a", "ac" costs 0, 1, 2 inserts: row = [0, 1, 2].

What happens in this step

word1 = "ab", word2 = "ac"
dp[0][0] = 0, dp[0][1] = 1, dp[0][2] = 2

Turning the empty string into a prefix of word2 of length j always takes j inserts — this row is the base case.
Step 1 of 3
4. Solution

Solution

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

  for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  return dp[m][n];
}
Time
O(m * n)
Space
O(m * n)
5. Test cases

Test cases

InputExpectedCovers
word1 = "horse", word2 = "ros"3example from the docstring
word1 = "intention", word2 = "execution"5a longer classic worked example
word1 = "abc", word2 = "abc"0identical strings need no edits
word1 = "", word2 = "abc"3building a string entirely from inserts
word1 = "abc", word2 = ""3reducing a string entirely with deletes
word1 = "", word2 = ""0smallest valid input, both strings empty
word1 = "a", word2 = "b"1a single replace operation
word1 = "a", word2 = "ab"1a single insert operation

Keep reading