Problem overview
The method minDistance(word1, word2) receives two strings and returns the fewest operations that turn word1 into word2. There are three operations and each costs one: insert a character anywhere, delete a character, or replace a character with another one.
For word1 = "horse" and word2 = "ros" the answer is 3: replace h with r to get rorse, delete the second r to get rose, delete e to get ros. For "intention" and "execution" the answer is 5. For an empty word1 and "abc" it is 3, three inserts. Either word can be empty.
Approach: solve every pair of prefixes
Trying every sequence of operations is far too slow. The lesson solves smaller versions of the problem instead. Let dp[i][j] be the fewest operations that turn the first i characters of word1 into the first j characters of word2. The table has (m + 1) × (n + 1) entries, where m and n are the word lengths, and the answer is dp[m][n].
Row 0 and column 0 stand for an empty prefix. Turning i characters into nothing takes i deletes, so dp[i][0] = i. Turning nothing into j characters takes j inserts, so dp[0][j] = j.
For every other entry, look at the last characters of the two prefixes, word1[i - 1] and word2[j - 1]. The prefix of length i ends at index i - 1, because strings count from 0 while the table counts characters.
- They are equal. They need no operation, so
dp[i][j] = dp[i - 1][j - 1]. Spending an operation on either of them is never better. - They differ. One operation fixes the end, and
dp[i][j]is 1 plus the smallest of three neighbours:dp[i - 1][j - 1]for a replace: both prefixes then lose their last character;dp[i - 1][j]for a delete ofword1's last character: only the prefix ofword1gets shorter;dp[i][j - 1]for an insert ofword2's last character at the end: it matches the end ofword2's prefix, which is then one shorter.
Filling the table row by row and left to right means the three neighbours (above, left and up-left) are always filled before they are needed.
For "horse" and "ros" the finished table is below. Rows are the prefixes of horse (the empty prefix, then h, ho, and so on) and columns are the prefixes of ros:
0 1 2 3
1 1 2 3
2 2 1 2
3 2 2 2
4 3 3 2
5 4 4 3
The bottom-right entry, 3, is the answer.
Step by step
- Store both lengths in constants,
mforword1andnforword2. They come up often. - Create the table
dp:m + 1rows ofn + 1zeros, withArray.from({ length: m + 1 }, ...). The function passed toArray.fromruns once per row, so each row is its own array. - Fill column 0 with a loop for
ifrom 0 tom, settingdp[i][0]toi: that many deletes. - Fill row 0 with a loop for
jfrom 0 ton, settingdp[0][j]toj: that many inserts. The entrydp[0][0]is set twice, both times to 0. - Loop over the rest of the table. The outer loop runs
ifrom 1 tom, and the inner one runsjfrom 1 ton, because row 0 and column 0 are already done. - Handle equal last characters with
if: copydp[i - 1][j - 1]. - Handle different last characters in the
else: take1 + Math.min(...)of the three neighbours. This is the key line. - Return
dp[m][n]after the loops.
The solution in JavaScript
class Solution {
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];
}
}
The JavaScript details worth knowing:
- Building a two-dimensional array.
Array.from({ length: m + 1 }, fn)treats the object as an array-like of lengthm + 1and callsfnonce per index, keeping what it returns. Every call makes a freshnew Array(n + 1).fill(0). - The shared-row trap.
new Array(m + 1).fill(new Array(n + 1).fill(0))looks equivalent but puts the same row object in every slot. Settingdp[0][1] = 9on a table built that way changes every row: it gives[[0,9,0],[0,9,0]]for two rows of three. - Reading a character.
word1[i - 1]gives a one-character string, and===compares two such strings by value. For an empty word the loops simply don't run. Math.minwith several arguments. It accepts any number of values, so the three neighbours go in directly.- Length versus index. The table index
icounts characters, while the string index of the last one isi - 1. Mixing them up is the most common bug in this kind of table.
Complexity
Time: O(m · n). The table has (m + 1) × (n + 1) entries, and each one takes a constant amount of work.
Space: O(m · n). The lesson keeps the whole table because it is easier to follow. Each row reads only itself and the row above it, so two rows of n + 1 numbers would be enough and would bring the space down to O(n).
Edge cases and common mistakes
- Empty words.
minDistance("", "abc")returns 3,minDistance("abc", "")returns 3 andminDistance("", "")returns 0. The border loops handle all three without special code. - Equal words.
minDistance("abc", "abc")returns 0, since every comparison takes the diagonal. - Single characters.
minDistance("a", "b")returns 1, one replace. - Forgetting the
+ 1. Without it, a mismatch would cost nothing, and the table would never grow. - Table one entry too small. A table of
mbynhas no room for the empty prefixes. That is why both dimensions have the extra+ 1. - Comparing
word1[i]withword2[j]. The prefix of lengthiends at indexi - 1, so this compares the wrong characters and can read past the end of a word. - Treating replace as free. A replace costs 1, like an insert or a delete. Only equal characters are free.
Testing
"horse"and"ros"give3."intention"and"execution"give5.""and"abc"give3."abc"and"abc"give0."a"and"b"give1.
