1. Empty prefix cost
Converting empty to length k needs k inserts or deletes.
i === 0 ? j : j === 0 ? i : 0Typorithm · hard
Edit Distance
▷ Interactive algorithm labedit-distance-dpdynamic-programmingtwo-strings2d-dpminimization
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Edit Distance
Dynamic Programming
Edit Distance finds the minimum insert, delete, and replace operations between two strings.
Each cell compares two prefixes.
Equal characters carry over the diagonal.
Different characters add one operation to the best edit choice.
Preparing algorithm lab…
01
State: min edits between prefixes.
02
Base: empty prefix costs length.
03
Match: diagonal.
04
Mismatch: 1 + min(delete, insert, replace).
function minDistance(word1, word2) {
const dp = Array.from({ length: word1.length + 1 }, (_, i) =>
Array.from({ length: word2.length + 1 }, (_, j) => (i === 0 ? j : j === 0 ? i : 0)),
);
for (let i = 1; i <= word1.length; i++) {
for (let j = 1; j <= word2.length; 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], dp[i][j - 1], dp[i - 1][j - 1]);
}
}
}
return dp[word1.length][word2.length];
}Read the implementation
Connect each part of the code to the concept before you type.
2. No edit
Equal chars cost nothing new.
dp[i][j] = dp[i - 1][j - 1]3. Edit choice
Try delete, insert, or replace.
1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.