The edit distance between two strings is the minimum number of single-character edits needed to turn one into the other, where each edit is an insert, a delete, or a replace and every edit costs 1. This is the classic Levenshtein distance (LeetCode 72): given word1 and word2, return the fewest operations that transform word1 into word2. It is the measure behind spell-checkers, fuzzy search, and DNA-sequence comparison — anywhere you need to score how far apart two strings are. See Levenshtein distance for background.
editDistance(word1, word2) // two strings -> minimum edit count (a number)editDistance('horse', 'ros'); // 3 (replace h→r, delete r, delete e)
editDistance('ab', 'abc'); // 1 (insert one character)
editDistance('', 'abc'); // 3 (insert every character)
editDistance('abcde', 'abcde'); // 0 (already identical)1; matching a character that is already correct costs nothing.editDistance(a, b) always equals editDistance(b, a), because an insert in one direction is a delete in the other.'' to any string is that string's length (you insert every character), and the same the other way.0 only when the two strings are already identical. Comparison is case-sensitive, and you should build the function yourself without a library.We are measuring how far apart two strings are — the fewest single-character edits that rewrite one into the other — by filling a small grid one cell at a time.
Your spell-checker sees teh and wants to know how close it is to the; a diff tool wants to know how much a line changed; a search box wants to forgive one typo. All three are asking the same question: how many one-character edits does it take to turn one string into another? An edit is an insert, a delete, or a replace, and each one costs 1. editDistance('horse', 'ros') is 3 because you can replace h with r, delete the leftover r, and delete the e — and no shorter sequence exists.
Picture turning word1 into word2 one keystroke at a time. At every step you may do exactly one of three things, and each counts as a single edit: insert a character, delete a character, or replace one character with another. The edit distance is the length of the shortest such sequence of moves. Everything else below is just a way to search every possible sequence without redoing the same work.
The moves suggest a direct recursion. Compare the last character of each string. If they are equal, no edit is needed there, so recurse on both strings with that character chopped off. If they differ, try all three edits on the last character and keep the cheapest — each edit costs 1 plus whatever the shorter subproblem costs.
function editDistance(word1, word2) {
const m = word1.length;
const n = word2.length;
// If either string is empty, the only option is to insert (or delete) the
// whole of the other one — that many edits.
if (m === 0) return n;
if (n === 0) return m;
// Last characters already match: no edit here, shrink both by one.
if (word1[m - 1] === word2[n - 1]) {
return editDistance(word1.slice(0, m - 1), word2.slice(0, n - 1));
}
// Otherwise pay 1 and take the cheapest of the three edits.
return 1 + Math.min(
editDistance(word1.slice(0, m - 1), word2.slice(0, n - 1)), // replace
editDistance(word1.slice(0, m - 1), word2), // delete
editDistance(word1, word2.slice(0, n - 1)), // insert
);
}This is correct, but it is unusably slow. The three recursive calls overlap: computing the distance for horse / ros needs hors / ro, and so does the distance for hors / ros, and each of those re-explores the same smaller prefixes again. The number of calls grows roughly like 3 to the power of the combined length — the classic sign of overlapping subproblems. The fix is to compute each (prefix of word1, prefix of word2) pair once and remember it. That memory is a two-dimensional table, and filling it directly bottom-up is the dynamic-programming solution.
function editDistance(word1, word2) {
const m = word1.length;
const n = word2.length;
// dp[i][j] = edit distance between the first i characters of word1 and the
// first j characters of word2. The table is (m + 1) by (n + 1) so that row 0
// and column 0 can hold the empty-prefix base cases.
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
// Base cases along the empty-prefix edges.
for (let j = 0; j <= n; j++) dp[0][j] = j; // insert j chars into an empty word1
for (let i = 0; i <= m; i++) dp[i][0] = i; // delete i chars down to an empty word2
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
// dp indices lead the string indices by one, so the characters that line
// up at this cell are word1[i - 1] and word2[j - 1].
if (word1[i - 1] === word2[j - 1]) {
// Characters match: no edit needed, carry the diagonal across for free.
dp[i][j] = dp[i - 1][j - 1];
} else {
// Mismatch: pay 1 for the cheapest of the three edits.
dp[i][j] = 1 + Math.min(
dp[i - 1][j - 1], // replace
dp[i - 1][j], // delete from word1
dp[i][j - 1], // insert into word1
);
}
}
}
return dp[m][n];
}
module.exports = { editDistance };Reading the table is the whole idea. dp[i][j] is the edit distance between the first i characters of word1 and the first j characters of word2, so the answer we want is dp[m][n] in the far corner. Every interior cell is decided by just three already-filled neighbours: the diagonal dp[i-1][j-1] (a replace, or a free ride when the two characters match), the cell above dp[i-1][j] (a delete), and the cell to the left dp[i][j-1] (an insert). Because each cell is filled once, the whole thing runs in O(m * n) time instead of exponential.
Take editDistance('horse', 'ros'). Rows stand for the prefixes of horse and columns for the prefixes of ros, both starting from the empty string ε. The base row and column fill in immediately: turning the empty string into ros needs 0, 1, 2, 3 inserts, and turning the prefixes of horse into the empty string needs 0, 1, 2, 3, 4, 5 deletes.
Now fill the interior, one cell at a time:
dp[1][1] compares h with r — a mismatch, so 1 + min(0, 1, 1) = 1.dp[2][2] compares o with o — a match, so it copies its diagonal dp[1][1] = 1 for free.dp[3][1] compares r with r — a match, copying dp[2][0] = 2.dp[4][3] compares s with s — a match, copying dp[3][2] = 2.dp[5][3] compares e with s — a mismatch, so 1 + min(dp[4][2], dp[4][3], dp[5][2]) = 1 + min(3, 2, 4) = 3.The answer is simply the bottom-right corner: dp[5][3] = 3.
(m + 1) by (n + 1), not m by n — that extra first row and first column are the empty-prefix base cases (dp[0][j] = j, dp[i][0] = i). Skip them and you have nowhere for the diagonal, up, and left neighbours of the first real cell to come from.word1[i - 1] and word2[j - 1] — the dp indices lead the string positions by one because row/column 0 is the empty prefix. Comparing word1[i] with word2[j] instead reads one character too far and silently returns wrong answers (or undefined off the end).1 — when word1[i - 1] === word2[j - 1] the cost is exactly dp[i - 1][j - 1]. Writing 1 + dp[i - 1][j - 1] for the match case charges for an edit that never happened and inflates every distance.O(min(m, n)) — each row depends only on the row above it, so you can keep just two rows (or one row plus a saved diagonal) instead of the whole grid. Loop over the shorter string in the inner dimension to make that one row as small as possible.dp[m][n]: at each cell, whichever neighbour you came from tells you whether the step was a match, replace, delete, or insert, so you can print the actual sequence of operations.2 and an insert costs 3 (say, because deletions are cheaper than typing), replace the fixed 1 + with the per-operation cost inside the min. The structure is identical; only the numbers change.ab into ba in one edit instead of two. It adds one more candidate to the min that looks two cells back diagonally when the crossed characters line up.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.
The edit distance between two strings is the minimum number of single-character edits needed to turn one into the other, where each edit is an insert, a delete, or a replace and every edit costs 1. This is the classic Levenshtein distance (LeetCode 72): given word1 and word2, return the fewest operations that transform word1 into word2. It is the measure behind spell-checkers, fuzzy search, and DNA-sequence comparison — anywhere you need to score how far apart two strings are. See Levenshtein distance for background.
editDistance(word1, word2) // two strings -> minimum edit count (a number)editDistance('horse', 'ros'); // 3 (replace h→r, delete r, delete e)
editDistance('ab', 'abc'); // 1 (insert one character)
editDistance('', 'abc'); // 3 (insert every character)
editDistance('abcde', 'abcde'); // 0 (already identical)1; matching a character that is already correct costs nothing.editDistance(a, b) always equals editDistance(b, a), because an insert in one direction is a delete in the other.'' to any string is that string's length (you insert every character), and the same the other way.0 only when the two strings are already identical. Comparison is case-sensitive, and you should build the function yourself without a library.We are measuring how far apart two strings are — the fewest single-character edits that rewrite one into the other — by filling a small grid one cell at a time.
Your spell-checker sees teh and wants to know how close it is to the; a diff tool wants to know how much a line changed; a search box wants to forgive one typo. All three are asking the same question: how many one-character edits does it take to turn one string into another? An edit is an insert, a delete, or a replace, and each one costs 1. editDistance('horse', 'ros') is 3 because you can replace h with r, delete the leftover r, and delete the e — and no shorter sequence exists.
Picture turning word1 into word2 one keystroke at a time. At every step you may do exactly one of three things, and each counts as a single edit: insert a character, delete a character, or replace one character with another. The edit distance is the length of the shortest such sequence of moves. Everything else below is just a way to search every possible sequence without redoing the same work.
The moves suggest a direct recursion. Compare the last character of each string. If they are equal, no edit is needed there, so recurse on both strings with that character chopped off. If they differ, try all three edits on the last character and keep the cheapest — each edit costs 1 plus whatever the shorter subproblem costs.
function editDistance(word1, word2) {
const m = word1.length;
const n = word2.length;
// If either string is empty, the only option is to insert (or delete) the
// whole of the other one — that many edits.
if (m === 0) return n;
if (n === 0) return m;
// Last characters already match: no edit here, shrink both by one.
if (word1[m - 1] === word2[n - 1]) {
return editDistance(word1.slice(0, m - 1), word2.slice(0, n - 1));
}
// Otherwise pay 1 and take the cheapest of the three edits.
return 1 + Math.min(
editDistance(word1.slice(0, m - 1), word2.slice(0, n - 1)), // replace
editDistance(word1.slice(0, m - 1), word2), // delete
editDistance(word1, word2.slice(0, n - 1)), // insert
);
}This is correct, but it is unusably slow. The three recursive calls overlap: computing the distance for horse / ros needs hors / ro, and so does the distance for hors / ros, and each of those re-explores the same smaller prefixes again. The number of calls grows roughly like 3 to the power of the combined length — the classic sign of overlapping subproblems. The fix is to compute each (prefix of word1, prefix of word2) pair once and remember it. That memory is a two-dimensional table, and filling it directly bottom-up is the dynamic-programming solution.
function editDistance(word1, word2) {
const m = word1.length;
const n = word2.length;
// dp[i][j] = edit distance between the first i characters of word1 and the
// first j characters of word2. The table is (m + 1) by (n + 1) so that row 0
// and column 0 can hold the empty-prefix base cases.
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
// Base cases along the empty-prefix edges.
for (let j = 0; j <= n; j++) dp[0][j] = j; // insert j chars into an empty word1
for (let i = 0; i <= m; i++) dp[i][0] = i; // delete i chars down to an empty word2
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
// dp indices lead the string indices by one, so the characters that line
// up at this cell are word1[i - 1] and word2[j - 1].
if (word1[i - 1] === word2[j - 1]) {
// Characters match: no edit needed, carry the diagonal across for free.
dp[i][j] = dp[i - 1][j - 1];
} else {
// Mismatch: pay 1 for the cheapest of the three edits.
dp[i][j] = 1 + Math.min(
dp[i - 1][j - 1], // replace
dp[i - 1][j], // delete from word1
dp[i][j - 1], // insert into word1
);
}
}
}
return dp[m][n];
}
module.exports = { editDistance };Reading the table is the whole idea. dp[i][j] is the edit distance between the first i characters of word1 and the first j characters of word2, so the answer we want is dp[m][n] in the far corner. Every interior cell is decided by just three already-filled neighbours: the diagonal dp[i-1][j-1] (a replace, or a free ride when the two characters match), the cell above dp[i-1][j] (a delete), and the cell to the left dp[i][j-1] (an insert). Because each cell is filled once, the whole thing runs in O(m * n) time instead of exponential.
Take editDistance('horse', 'ros'). Rows stand for the prefixes of horse and columns for the prefixes of ros, both starting from the empty string ε. The base row and column fill in immediately: turning the empty string into ros needs 0, 1, 2, 3 inserts, and turning the prefixes of horse into the empty string needs 0, 1, 2, 3, 4, 5 deletes.
Now fill the interior, one cell at a time:
dp[1][1] compares h with r — a mismatch, so 1 + min(0, 1, 1) = 1.dp[2][2] compares o with o — a match, so it copies its diagonal dp[1][1] = 1 for free.dp[3][1] compares r with r — a match, copying dp[2][0] = 2.dp[4][3] compares s with s — a match, copying dp[3][2] = 2.dp[5][3] compares e with s — a mismatch, so 1 + min(dp[4][2], dp[4][3], dp[5][2]) = 1 + min(3, 2, 4) = 3.The answer is simply the bottom-right corner: dp[5][3] = 3.
(m + 1) by (n + 1), not m by n — that extra first row and first column are the empty-prefix base cases (dp[0][j] = j, dp[i][0] = i). Skip them and you have nowhere for the diagonal, up, and left neighbours of the first real cell to come from.word1[i - 1] and word2[j - 1] — the dp indices lead the string positions by one because row/column 0 is the empty prefix. Comparing word1[i] with word2[j] instead reads one character too far and silently returns wrong answers (or undefined off the end).1 — when word1[i - 1] === word2[j - 1] the cost is exactly dp[i - 1][j - 1]. Writing 1 + dp[i - 1][j - 1] for the match case charges for an edit that never happened and inflates every distance.O(min(m, n)) — each row depends only on the row above it, so you can keep just two rows (or one row plus a saved diagonal) instead of the whole grid. Loop over the shorter string in the inner dimension to make that one row as small as possible.dp[m][n]: at each cell, whichever neighbour you came from tells you whether the step was a match, replace, delete, or insert, so you can print the actual sequence of operations.2 and an insert costs 3 (say, because deletions are cheaper than typing), replace the fixed 1 + with the per-operation cost inside the min. The structure is identical; only the numbers change.ab into ba in one edit instead of two. It adds one more candidate to the min that looks two cells back diagonally when the crossed characters line up.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.