Tags:
Medium
Skills:
DP
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Cần tìm số step để có thể convert word1 to word2 ít nhất (insert, delete, replace)
Approach
Gọi dp[i][j] là số phép biến đổi tối thiểu để biến word1[0..i-1] thành word2[0..j-1].
word1[i-1] === word2[j-1], không cần thao tác gì thêm:dp[i][j] = dp[i-1][j-1]
dp[i][j-1] + 1dp[i-1][j] + 1dp[i-1][j-1] + 1dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
dp[word1.length][word2.length] là đáp án cuối cùng.
Time and space complexity
Solution- Bottom up DP
1function minDistance(word1: string, word2: string): number {
2 const n = word1.length;
3 const m = word2.length;
4
5 const dp: number[][] = Array.from({ length: n + 1 }, () => Array(m + 1).fill(0))
6
7 for (let i = 0; i <= n; i++) {
8 dp[i][0] = i;
9 }
10
11 for (let j = 0; j <= m; j++) {
12 dp[0][j] = j;
13 }
14
15 for (let i = 1; i <= n; i++) {
16 for (let j = 1; j <= m; j++) {
17 if (word1[i - 1] === word2[j - 1]) {
18 dp[i][j] = dp[i - 1][j - 1];
19 } else {
20 dp[i][j] = Math.min(
21 dp[i - 1][j],
22 dp[i][j - 1],
23 dp[i - 1][j - 1]
24 ) + 1
25 }
26 }
27 }
28
29 return dp[n][m]
30}dp[n][m] (n: độ dài word1, m: độ dài word2)word1[i - 1] === word2[j - 1] và dp[i][j] === dp[i - 1][j - 1] → Không thao tác, giữ nguyên ký tựdp[i][j] == dp[i][j-1] + 1→ Insert (chèn ký tự word2[j-1] vào word1).
dp[i][j] == dp[i-1][j] + 1→ Delete (xóa ký tự word1[i-1]).
dp[i][j] == dp[i-1][j-1] + 1→ Replace (thay word1[i-1] thành word2[j-1]).
1for (let i = 0; i <= n; i++) {
2 dp[i][0] = i;
3}
4
5for (let j = 0; j <= m; j++) {
6 dp[0][j] = j;
7}| "" | x | y | |
| “” | 0 | 1 | 2 |
| a | 1 | 0 + 1 | 1 + 1 ? Tại sao là 2? |
| b | 2 | ||
| c | 3 |
Solution: Top Down DP
SC: O(n * m)
1function minDistance(word1: string, word2: string): number {
2 const memo: Map<string, number> = new Map();
3 cosnt dfs(word1.length, word2.length, word1, word2, memo)
4}
5
6function dfs(i: number, j: number, word1: string, word2: string, memo: Map<string, number>) {
7 const key = `${i},${j}`;
8 if(memo.has(key)) return memo.get(key)!;
9
10 if(i === 0) return j;
11 if(j === 0) return i;
12
13 if(word1[i - 1] === word2[j - 1]) {
14 const res = dfs(i - 1, j - 1, word1, word2, memo);
15 memo.set(key, res)
16 return res;
17 }
18
19 const delete = dfs (i - 1, j, word1, word2, memo);
20 const insert = dfs(i, j - 1, word1, word2, memo);
21 const replace = dfs(i - 1, j - 1, word1, word2, memo);
22
23 const res = Math.min(delete, insert, replace) + 1;
24 memo.set(key, res);
25
26 return res
27}