Decode Ways

Bài toán

Một thông điệp chứa các chữ cái từ A-Z được mã hóa thành số theo quy tắc: 'A' -> "1" 'B' -> "2" ... 'Z' -> "26"

Cho chuỗi số s, hãy đếm số cách giải mã lại thành chữ.

Ví dụ:

text:

Input: s = "12"
Output: 2
Cách: "AB" (1, 2) hoặc "L" (12).

Input: s = "226"
Output: 3
Cách: "BZ" (2, 26), "VF" (22, 6), "BBF" (2, 2, 6).

Input: s = "06"
Output: 0 (Không hợp lệ vì '0' không map với ai cả, và không được bắt đầu bằng 0).

Phân Tích & Tiếp Cận

Logic QHĐ

Ta dùng dp[i] là số cách giải mã chuỗi s[0...i]. Tại ký tự s[i]:

Nếu xem nó là 1 chữ số riêng lẻ: Nếu s[i] !== '0', ta có thể cộng thêm số cách của dp[i-1].
Nếu xem nó gộp với ký tự trước (s[i-1]s[i]):
- Nếu số tạo thành nằm trong khoảng [10, 26], ta có thể cộng thêm số cách của dp[i-2].

Base Case

dp[0] = 1 (Chuỗi rỗng có 1 cách là không làm gì cả).

typescript:

function numDecodings(s: string): number {
    // DP mảng kích thước n+1
    const dp = new Array(s.length + 1).fill(0);
    
    dp[0] = 1; // Base case cho trường hợp chuỗi rỗng
    dp[1] = s[0] === '0' ? 0 : 1; // Ký tự đầu tiên

    for (let i = 2; i <= s.length; i++) {
        const oneDigit = Number(s.substring(i - 1, i)); // s[i-1]
        const twoDigits = Number(s.substring(i - 2, i)); // s[i-2...i-1]

        // Nếu 1 chữ số hợp lệ (1-9)
        if (oneDigit >= 1 && oneDigit <= 9) {
            dp[i] += dp[i - 1];
        }

        // Nếu 2 chữ số hợp lệ (10-26)
        if (twoDigits >= 10 && twoDigits <= 26) {
            dp[i] += dp[i - 2];
        }
    }

    return dp[s.length];
}

Tối ưu Space

Tương tự Climbing Stairs, dp[i] chỉ phụ thuộc dp[i-1] và dp[i-2]. Có thể rút gọn còn 2 biến.

Time Complexity: $O(n)$.
Space Complexity: $O(n)$ (hoặc $O(1)$ nếu tối ưu).

Pattern Nhận Diện

Dạng bài Partition/Splitting string.
Cần xử lý kỹ các trường hợp biên (0 đứng đầu, 0 đứng sau 30, 40...).

Bài trước

Coin Change

Bài tiếp theo

Palindromic Substrings