Return the minimum number of operations (insert a character, delete a character, or replace a character) needed to convert word1 into word2.
dp[i][j] = edits to turn the first i letters of word1 into the first j of word2. Matching letters copy the diagonal; otherwise 1 + min(left = insert, up = delete, diagonal = replace).
1function minDistance(a: string, b: string): number {2const dp = Array.from({ length: a.length + 1 }, (_, i) => Array.from({ length: b.length + 1 }, (_, j) => (i ? (j ? 0 : i) : j)));3for (let i = 1; i <= a.length; i++)4for (let j = 1; j <= b.length; j++)5dp[i][j] = a[i - 1] === b[j - 1]6? dp[i - 1][j - 1]7: 1 + Math.min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]);8return dp[a.length][b.length];9}
| ∅ | r | o | s | |
|---|---|---|---|---|
| ∅ | 0 | 1 | 2 | 3 |
| h | 1 | |||
| o | 2 | |||
| r | 3 | |||
| s | 4 | |||
| e | 5 |
Turning a prefix into the empty string (or back) costs its length.
Space: play/pause · ←/→: step