91. Decode Ways
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
Bài toán yêu cầu đếm số cách giải mã một chuỗi số thành các ký tự từ 'A' đến 'Z', với quy ước: 'A' = 1, 'B' = 2, ..., 'Z' = 26.
Approach
Công thức DP
Gọi dp[i] là số cách giải mã cho chuỗi s[0..i-1]:
dp[i] += dp[i-1] (giải mã một ký tự).dp[i] += dp[i-2] (giải mã hai ký tự).Solution - Bottom up dp
1function numDecodings(s: string): number {
2 const n = s.length;
3 if (n === 0) return 0;
4
5 const dp: number[] = Array(n + 1).fill(0);
6 dp[0] = 1
7 dp[1] = s[0] !== '0' ? 1 : 0;
8
9 for (let i = 2; i <= n; i++) {
10 if (s[i - 1] !== '0') {
11 dp[i] = dp[i] + dp[i - 1];
12 }
13 const two_digit = Number(s.slice(i - 2, i));
14 if (two_digit >= 10 && two_digit <= 26) {
15 dp[i] = dp[i] + dp[i - 2];
16 }
17 }
18
19 return dp[n];
20};Solution - Optimize
1function numDecodings(s: string): number {
2 const n = s.length;
3 let prev = 0; // dp[i - 2];
4 let curr = 1; // dp[i - 1];
5 for (let i = 1; i <= n; i++) {
6 let temp = 0;
7 if (s[i - 1] !== '0') {
8 temp += curr;
9 }
10
11 if (i > 1 && (s[i - 2] === '1' || (s[i - 2] === '2' && s[i - 1] <= '6'))) {
12 temp += prev;
13 }
14
15 prev = curr;
16 curr = temp;
17 }
18
19 return curr;
20};