#72 - Edit Distance
MediumDP - Multidimensional
Given two strings word1 and word2, return the minimum number of operations (insert, delete, replace a character) required to convert word1 into word2.
| Input | Output |
|---|---|
word1 = "horse", word2 = "ros" | 3 |
word1 = "intention", word2 = "execution" | 5 |
Solution Space
ts
/**
* Returns the minimum edit distance (Levenshtein distance) between two strings.
*
* dp[i][j] = min operations to convert word1[0..i) into word2[0..j).
* - Match: dp[i-1][j-1]
* - Replace: dp[i-1][j-1] + 1
* - Insert: dp[i][j-1] + 1
* - Delete: dp[i-1][j] + 1
*
* @param word1 Source string
* @param word2 Target string
* @returns Minimum number of operations
*/
export function minDistance(word1: string, word2: string): number {
const m = word1.length;
const n = word2.length;
const dp: number[][] = Array.from({ length: m + 1 }, () =>
new Array(n + 1).fill(0),
);
// Base cases: converting to/from empty string
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], // replace
dp[i - 1][j], // delete
dp[i][j - 1], // insert
);
}
}
}
return dp[m][n];
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
Approach: 2D DP – classic edit distance recurrence. Characters match → take diagonal. Otherwise → 1 + min(replace, delete, insert).
Time: O(m · n) – fill the entire table.
Space: O(m · n) – the DP table.
Alternative approaches:
| Approach | Idea | Time | Space |
|---|---|---|---|
| Space-optimized 1D DP | Keep only two rows since dp[i] depends only on dp[i-1] | O(m · n) | O(min(m, n)) |
Why the 2D approach is preferred: clearer to implement and debug; the 1D optimization is a straightforward follow-up once correctness is confirmed.