Decode Ways: DP với transition có điều kiện

Đây là bài đầu tiên trong series khiến tôi phải dừng lại và đọc lại đề hai lần. Không phải vì nó khó — mà vì nó trông y hệt Climbing Stairs cho đến khi bạn nhìn kỹ hơn. Công thức truy hồi vẫn là "cộng hai bước trước", nhưng mỗi bước có một cái gate: ký tự có hợp lệ không, hai ký tự ghép lại có nằm trong alphabet không. Bỏ sót một gate là đếm sai. Và đó là điểm khác biệt duy nhất, nhưng nó đủ để biến bài toán thành thứ cần suy nghĩ thật sự.

Đề bài

Cho chuỗi s gồm các chữ số, đếm số cách decode hợp lệ dùng ánh xạ "1" -> 'A', "2" -> 'B', ..., "26" -> 'Z'. Ký tự '0' không thể decode một mình, và số 0 đứng đầu làm nhóm 2 ký tự không hợp lệ. Đề đầy đủ: LeetCode 91.

Ràng buộc:
- 1 <= s.length <= 100
- s chỉ chứa chữ số và có thể có số 0 đứng đầu.

Constraint 1 <= s.length <= 100 — đáp án vừa 32-bit integer, không có gì đáng ngại về overflow hay độ dài chuỗi. Thách thức nằm ở logic. Với tối đa 100 ký tự, ngay cả recursion brute force không có memoization cũng sẽ không bị timeout, vì cây recursion phân nhánh tối đa 2 lần mỗi node và sâu tối đa 100. Memoization ở đây phục vụ tính đúng đắn của lập luận, không phải sống sót dưới constraint.

Hai điều kiện gate tại mỗi vị trí:

1. Bước 1 ký tự: s[i] != '0' — nếu ký tự hiện tại là '0', không decode được một mình.
2. Bước 2 ký tự: s[i..i+1] phải nằm trong [10, 26] — bắt đầu bằng '1' hoặc '2', và nếu là '2' thì chữ số thứ hai không được vượt quá '6'.

Climbing Stairs không có điều kiện nào cả — bạn luôn có thể bước 1 hoặc 2. Decode Ways có thể chặn cả hai bước tại cùng một vị trí — lúc đó dp[i] = 0 hoàn toàn.

Giới hạn alphabet tại 26 không phải ngẫu nhiên — nó chính là thứ giới hạn nhóm 2 ký tự trong [10, 26] và loại bỏ hoàn toàn mọi thứ bắt đầu bằng '0'. Một '0' xuất hiện giữa chuỗi là một bẫy im lặng: nó giết bước 1 ký tự tại vị trí đó, và chỉ có thể được "cứu" bởi ký tự '1' hoặc '2' đứng trước — tạo thành "10" hoặc "20".

Nhận dạng pattern

Các keyword hay gặp ở dạng bài này: "number of ways", "decode", "partition string into valid segments". Khi bài toán yêu cầu chia một chuỗi thành các đoạn hợp lệ và đếm số cách, bạn đang nhìn vào gated linear DP.

Điểm quan trọng: ở bài này, mỗi nhóm chỉ gồm 1 hoặc 2 ký tự (map vào 1..26). Nhờ vậy lookahead bị chặn ở i+1 và i+2. Nếu nhóm hợp lệ có thể dài tuỳ ý, bạn cần Word Break. Ở đây không cần — và đó là lý do tại sao sau này có thể tối ưu xuống O(1) space.

Approach 1: Top-Down với memoization

Cách tự nhiên nhất: đứng ở vị trí index và hỏi "tôi có thể tiêu thụ 1 ký tự từ đây không, và 2 ký tự không?" Mỗi lựa chọn hợp lệ đóng góp vào tổng số cách.

class Solution:
    def numDecodings(self, s: str) -> int:
        memo = {}
        def decode(index):
            if index == len(s):
                return 1
            if index in memo:
                return memo[index]
            if s[index] == '0':
                memo[index] = 0
                return 0
            result = decode(index + 1)
            if index + 1 < len(s):
                two_digit = int(s[index:index+2])
                if 10 <= two_digit <= 26:
                    result += decode(index + 2)
            memo[index] = result
            return result
        return decode(0)

Để thấy cấu trúc phân nhánh, đây là cây recursion cho s = "226". Các node trả về 0 là dead end; node đánh dấu *memo* là đã được tính trước và chỉ cần trả về:

Trace s = "12" để xác nhận code. decode(0): s[0]='1', không phải '0', nên result = decode(1). Sau đó kiểm tra "12" = 12, nằm trong [10, 26], nên result += decode(2). decode(1): s[1]='2', result = decode(2) = 1, không đủ chỗ cho 2 ký tự. decode(2) là base case, trả về 1. Vậy decode(1) = 1, decode(0) = 1 + 1 = 2. Hai cách: "A-B" và "L". Đúng.

Memoization ở đây bắt buộc. Không có nó, các subproblem chồng chéo nhau sẽ gây bùng nổ tổ hợp — giống như Fibonacci naive. Với memoization, mỗi index chỉ được tính một lần.

Bản C#:

public class Solution {
    private Dictionary<int, int> memo;
    private string s;
    public int NumDecodings(string s) {
        this.s = s;
        this.memo = new Dictionary<int, int>();
        return Decode(0);
    }
    private int Decode(int index) {
        if (index == s.Length) return 1;
        if (memo.ContainsKey(index)) return memo[index];
        if (s[index] == '0') { memo[index] = 0; return 0; }
        int result = Decode(index + 1);
        if (index + 1 < s.Length) {
            int twoDigit = int.Parse(s.Substring(index, 2));
            if (twoDigit >= 10 && twoDigit <= 26)
                result += Decode(index + 2);
        }
        memo[index] = result;
        return result;
    }
}

Time: O(n) — mỗi index được tính một lần. Space: O(n) cho cả memo dictionary và call stack.

Tôi thích bản top-down khi cần debug — call stack cho thấy rõ từng nhánh bị chặn ở đâu. Nhưng recursion có overhead thật. Với n = 100, call stack tối đa là 100 frame, ổn, nhưng không cần thiết. Bước tiếp theo là lật ngược hướng.

Approach 2: Bottom-Up DP, điền từ phải sang trái

dp[i] = số cách decode chuỗi s[i:]. Base case: dp[n] = 1 (đã decode hết, một cách hợp lệ). Điền từ n-1 về 0.

Hướng điền quan trọng và khác với Climbing Stairs. Ở Climbing Stairs, dp[i] nhìn về sau (dp[i-1], dp[i-2]), nên đi trái sang phải. Ở Decode Ways, dp[i] nhìn về trước (dp[i+1], dp[i+2]), nên phải đi phải sang trái.

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        dp = [0] * (n + 1)
        dp[n] = 1
        for i in range(n - 1, -1, -1):
            if s[i] == '0':
                dp[i] = 0
            else:
                dp[i] = dp[i + 1]
                if i + 1 < n:
                    two_digit = int(s[i:i+2])
                    if 10 <= two_digit <= 26:
                        dp[i] += dp[i + 2]
        return dp[0]

Trace s = "226" từng bước:

dp[3] = 1                   // base: hết chuỗi
dp[2] = dp[3] = 1           // '6' != '0'; không đủ chỗ cho 2 ký tự
dp[1] = dp[2] + dp[3] = 2   // '2' != '0'; "26" = 26 thuộc [10,26]
dp[0] = dp[1] + dp[2] = 3   // '2' != '0'; "22" = 22 thuộc [10,26]

Ba cách. Đúng.

Trace s = "06":

dp[2] = 1
dp[1] = dp[2] = 1   // '6' != '0'
dp[0] = 0           // '0' -> chặn ngay

Trả về 0. Gate tại s[0] == '0' giết cả chuỗi — không có cách nào decode từ đầu.

Bản C# với full array:

public class Solution {
    public int NumDecodings(string s) {
        int n = s.Length;
        int[] dp = new int[n + 1];
        dp[n] = 1;
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == '0') {
                dp[i] = 0;
            } else {
                dp[i] = dp[i + 1];
                if (i + 1 < n) {
                    int twoDigit = int.Parse(s.Substring(i, 2));
                    if (twoDigit >= 10 && twoDigit <= 26)
                        dp[i] += dp[i + 2];
                }
            }
        }
        return dp[0];
    }
}

Time: O(n). Space: O(n) cho mảng dp đầy đủ. Hoạt động đúng — nhưng để ý: tại bước i, vòng lặp chỉ đọc dp[i+1] và dp[i+2]. Không bao giờ xa hơn. Đó là dấu hiệu bạn có thể bỏ hẳn mảng.

Bản tôi thực sự dùng: space-optimized O(1)

Thay vì giữ cả mảng, giữ hai biến: next1 là dp[i+1] và next2 là dp[i+2]. Sau mỗi bước, đẩy chúng lên. Bộ nhớ từ O(n) xuống O(1).

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        next1, next2 = 1, 1   # dp[n] = 1; sentinel dp[n+1] = 1
        for i in range(n - 1, -1, -1):
            current = 0
            if s[i] != '0':
                current = next1
                if i + 1 < n:
                    two_digit = int(s[i:i+2])
                    if 10 <= two_digit <= 26:
                        current += next2
            next2, next1 = next1, current
        return next1

Bản C# — đây là cái tôi thực sự để lại khi interview:

public class Solution {
    public int NumDecodings(string s) {
        int n = s.Length;
        int next1 = 1, next2 = 1;   // dp[i+1], dp[i+2]
        for (int i = n - 1; i >= 0; i--) {
            int current = 0;
            if (s[i] != '0') {
                current = next1;
                if (i + 1 < n) {
                    int twoDigit = (s[i] - '0') * 10 + (s[i + 1] - '0');
                    if (twoDigit >= 10 && twoDigit <= 26)
                        current += next2;
                }
            }
            next2 = next1;
            next1 = current;
        }
        return next1;
    }
}

Một chi tiết đáng chú ý ở bản C#: thay vì int.Parse(s.Substring(i, 2)), tính thủ công (s[i] - '0') * 10 + (s[i+1] - '0'). Không allocation, không parse. Nhỏ nhặt — nhưng là reflex đúng khi viết code trong tight loop.

Trace lại "226" với hai biến để xác nhận:

i=2: s[2]='6', current = next1 = 1; không có i+1  -> next2=1, next1=1
i=1: s[1]='2', current = next1 = 1; "26"=26 thuộc [10,26] -> current += next2=1 -> current=2
                                      next2=1, next1=2
i=0: s[0]='2', current = next1 = 2; "22"=22 thuộc [10,26] -> current += next2=1 -> current=3
                                      next2=2, next1=3
return next1 = 3  OK

Time: O(n). Space: O(1).

So sánh các approach

Cả ba đều O(n) thời gian — memoization đảm bảo không có index nào bị tính hai lần. Sự khác biệt thực sự nằm ở space.

Các edge case không được bỏ qua

Đây là những trường hợp hay xuất hiện trong interview vì chúng kiểm tra xem bạn có thực sự hiểu các gate hay không:

• s = "0": s[0] == '0' giết bước 1 ký tự ngay lập tức; không có bước 2 ký tự vì chỉ còn 1 ký tự. Trả về 0. Code xử lý bằng cách set current = 0 tại vòng lặp duy nhất và trả về next1 = 0.
• s = "10": i=1, s[1]='0' -> bước 1 ký tự chết, dp[1]=0. i=0, s[0]='1', bước 1 -> current = dp[1] = 0. Bước 2 ký tự: "10" = 10 thuộc [10, 26] -> current += 1. Trả về 1. Chỉ một cách: "J". '0' được hấp thụ bởi '1' đứng trước.
• s = "30": i=1, s[1]='0' -> 0. i=0, s[0]='3', bước 1 -> current = 0. "30" = 30 > 26, không có bước 2. Trả về 0. '3' không cứu được '0' vì 30 vượt quá giới hạn alphabet.
• s = "27": i=1, current = 1. i=0, bước 1 -> current = 1. "27" = 27 > 26, không có bước 2. Trả về 1. Chỉ một cách: "B-G". Đây là trường hợp "vừa vượt giới hạn" bắt lỗi off-by-one trong range check.
• s = "11106": Ba cách: (1,1,10,6), (11,10,6). Nhóm (1,11,06) không hợp lệ vì "06" không thuộc [10,26] — gate hai ký tự chặn nó. Code xử lý tự nhiên: khi i=3 và s[3]='0', dp[3]=0, nên mọi đường đi qua '0' đơn đóng góp 0.

Điểm mấu chốt: '0' là ký tự nguy hiểm nhất. Nó giết bước 1 ký tự hoàn toàn, và chỉ có thể được cứu bởi ký tự '1' hoặc '2' đứng trước — tạo thành "10" hoặc "20". Nếu '0' đứng sau bất kỳ ký tự nào khác ("30", "40", ...), nhánh đó chết.

Bức tranh lớn hơn trong series

Nhìn lại cả series: Climbing Stairs dạy cấu trúc cơ bản — cộng hai bước trước. Min Cost Climbing Stairs thêm chi phí vào mỗi bước. House Robber thêm ràng buộc bắt buộc bỏ qua một phần tử. Decode Ways thêm gate: một số bước có thể bị chặn hoàn toàn tùy vào nội dung của input.

Chuỗi tiến hoá đó không phải ngẫu nhiên. Mỗi bài thêm đúng một biến tấu, và biến tấu đó thay đổi cách viết recurrence. Khi gặp một bài DP mới, câu hỏi đúng không phải "bài này giống Climbing Stairs không?" mà là "transition bị gated bởi cái gì?" Nếu có điều kiện chặn bước chuyển, bạn đang ở dạng Decode Ways. Nếu không, bạn ở dạng Climbing Stairs.

Phản xạ cần rèn: nhìn vào recurrence, xác định gate, viết điều kiện trước khi viết phép cộng. Gate bị bỏ sót là lỗi logic — compiler không bắt được, và test case đơn giản thường không lộ ra ngay.

Các bài liên quan

Word Break (139) là phiên bản phi tuyến của cùng pattern. Thay vì nhìn 1 hoặc 2 bước với range check đơn giản, bạn nhìn tới độ dài của từ dài nhất trong dictionary. Gate logic tốn kém hơn nhưng cấu trúc giống hệt: tại mỗi vị trí, tôi có thể tiêu thụ k ký tự không? Kiểm tra dictionary; nếu có, kế thừa từ dp[i+k].

Climbing Stairs (70) là phiên bản không có gate. Cả hai transition luôn sẵn sàng — không có '0' guard, không có range check. Nếu giải được bài đó, bạn đã hiểu skeleton; Decode Ways chỉ thêm gate vào.

Jump Game II (45) đảo hướng. Thay vì đếm số đường đi, bạn minimize số bước nhảy. Nhưng câu hỏi "những vị trí nào có thể đến được vị trí i?" có cấu trúc giống hệt "những suffix nào tôi có thể decode từ vị trí i?"

Combination Sum IV (377) và Integer Break (343) đều thuộc vùng lân cận này — DP với lookahead cố định hoặc tuỳ ý, nơi mỗi state tích luỹ từ các predecessor hợp lệ với điều kiện tường minh.

Khi đã internalize gated transition, bạn sẽ bắt đầu thấy nó ở khắp nơi. Điều kiện guard thay đổi; hình dạng thì không.