Tổ hợp phím điện thoại: tại sao backtracking khớp hoàn hảo với bài này

Input là một chuỗi tối đa bốn chữ số, mỗi chữ số từ '2' đến '9'. Mỗi chữ số ánh xạ tới một nhóm chữ cái theo layout bàn phím T9 cũ. Nhiệm vụ là trả về mọi chuỗi có thể tạo ra bằng cách chọn đúng một chữ cái cho mỗi chữ số. Với "23" thì có chín chuỗi: từ "ad" đến "cf". Với "" thì là danh sách rỗng. Đơn giản để phát biểu, nhưng khoảng cách giữa cách implement lặp và đệ quy nói lên điều gì đó hữu ích về cách backtracking tư duy.

Đề bài

Cho một chuỗi chữ số từ '2' đến '9', trả về tất cả tổ hợp chữ cái có thể mà chuỗi số đó có thể biểu diễn trên bàn phím điện thoại, theo thứ tự bất kỳ. Input rỗng trả về danh sách rỗng. Full statement: LeetCode 17.

Ràng buộc:
- 0 <= digits.length <= 4
- digits[i] là chữ số trong khoảng ['2', '9'].

Constraint thực sự bắt buộc điều gì

0 <= digits.length <= 4. Một dòng duy nhất đó làm rất nhiều việc. Kích thước output tối đa là 4^4 = 256 chuỗi có độ dài 4 — tổng cộng 1024 ký tự. Đây không phải lãnh địa của O(n^2) vs O(n log n) nơi bạn cần tối ưu cẩn thận; bản thân output đã bị giới hạn bởi một hằng số nhỏ. Bạn phải liệt kê tất cả, và dù làm theo cách nào thì công việc cũng tỉ lệ với output.

Các chữ số chạy từ '2' đến '9'. Không có '0' hay '1' trong input — cả hai không được gán trên bàn phím điện thoại — vì vậy phép ánh xạ là hoàn chỉnh và không có khoảng trống cần xử lý. Bảy chữ số ánh xạ tới ba chữ cái mỗi cái; '7' và '9' ánh xạ tới bốn. Giới hạn 4^n trong trường hợp xấu nhất đến từ hai chữ số đó.

Những gì các constraint này không bảo bạn làm: prune, memoize, hay tránh allocate tất cả kết quả. Output phải chứa mọi tổ hợp dù sao đi nữa. Quyết định thực sự duy nhất là bạn build chúng như thế nào — tất cả cùng lúc theo từng layer, hay từng chuỗi hoàn chỉnh một via recursion.

Approach 1: mở rộng lặp (build từng layer theo kiểu BFS)

Bắt đầu với một list chứa một chuỗi rỗng. Với mỗi chữ số trong input, lấy mọi chuỗi partial hiện tại và mở rộng nó bằng mỗi chữ cái mà chữ số đó ánh xạ tới. Sau khi xử lý tất cả chữ số, list chứa kết quả hoàn chỉnh.

from typing import List
 
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
 
        phone_map = {
            '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
            '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
        }
 
        result = ['']
 
        for digit in digits:
            letters = phone_map[digit]
            new_result = []
            for combination in result:
                for letter in letters:
                    new_result.append(combination + letter)
            result = new_result
 
        return result

using System.Collections.Generic;
 
public class Solution {
    public IList<string> LetterCombinations(string digits) {
        if (string.IsNullOrEmpty(digits))
            return new List<string>();
 
        var phoneMap = new Dictionary<char, string> {
            {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
            {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
        };
 
        var result = new List<string> { "" };
 
        foreach (char digit in digits) {
            string letters = phoneMap[digit];
            var newResult = new List<string>();
            foreach (string combination in result) {
                foreach (char letter in letters) {
                    newResult.Add(combination + letter);
                }
            }
            result = newResult;
        }
 
        return result;
    }
}

Với "23", quá trình diễn ra như sau. Sau chữ số '2': result = ["a", "b", "c"]. Sau chữ số '3': mỗi trong ba chuỗi đó được mở rộng thêm d, e, f, tạo ra chín chuỗi. Xong.

Nhận xét chính là result ở mọi giai đoạn đại diện cho Cartesian product đầy đủ của các chữ số đã xem. Bạn đang build product tăng dần, một factor một lúc. Cách này hoạt động và dễ lý luận. Điểm yếu là bạn luôn giữ list intermediate đầy đủ trong bộ nhớ trong bước mở rộng — list cũ và list mới cùng tồn tại đồng thời.

Complexity: Time O(4^n * n) — tối đa 4^n tổ hợp, mỗi cái dài tới n. Space O(4^n * n) — bạn giữ list intermediate đầy đủ, và tại bước từ chữ số cuối, list cũ kích thước 4^(n-1) và list mới kích thước 4^n cùng tồn tại.

Approach 2: backtracking — từng chuỗi một

Thay vì duy trì list chuỗi partial đang lớn dần, recursion đi xuống cây quyết định theo depth-first: chọn một chữ cái cho vị trí chữ số hiện tại, recurse vào vị trí tiếp theo, thêm vào kết quả chỉ khi chuỗi hoàn chỉnh.

from typing import List
 
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
 
        phone_map = {
            '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
            '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
        }
 
        result = []
 
        def backtrack(index: int, current: str) -> None:
            if index == len(digits):
                result.append(current)
                return
            for letter in phone_map[digits[index]]:
                backtrack(index + 1, current + letter)
 
        backtrack(0, "")
        return result

using System.Collections.Generic;
using System.Text;
 
public class Solution {
    public IList<string> LetterCombinations(string digits) {
        if (string.IsNullOrEmpty(digits))
            return new List<string>();
 
        var phoneMap = new Dictionary<char, string> {
            {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
            {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
        };
 
        var result = new List<string>();
 
        void Backtrack(int index, StringBuilder current) {
            if (index == digits.Length) {
                result.Add(current.ToString());
                return;
            }
            foreach (char letter in phoneMap[digits[index]]) {
                current.Append(letter);
                Backtrack(index + 1, current);
                current.Remove(current.Length - 1, 1);
            }
        }
 
        Backtrack(0, new StringBuilder());
        return result;
    }
}

Chú ý sự khác biệt giữa C# và Python. Python string là immutable: current + letter tạo một string object mới mà không sửa current, vì vậy không cần bước undo tường minh. C# dùng StringBuilder (mutable) để hiệu quả hơn, nghĩa là bạn phải xóa ký tự cuối sau mỗi lần gọi đệ quy — bước backtrack kinh điển: thêm, recurse, xóa.

Complexity: Time O(4^n * n) — cùng bound với lặp, vì cùng lý do. Space O(n) cho call stack (độ sâu bằng digits.length, tối đa 4 level) cộng O(4^n * n) cho output list. Call stack nhỏ hơn nhiều so với các allocation intermediate của approach lặp.

Trace tay qua "23"

backtrack(index=0, current="")
  digit='2', letters="abc"
  -> letter='a': backtrack(index=1, current="a")
       digit='3', letters="def"
       -> letter='d': backtrack(index=2, current="ad")  [base: append "ad"]
       -> letter='e': backtrack(index=2, current="ae")  [base: append "ae"]
       -> letter='f': backtrack(index=2, current="af")  [base: append "af"]
  -> letter='b': backtrack(index=1, current="b")
       -> letter='d': append "bd"
       -> letter='e': append "be"
       -> letter='f': append "bf"
  -> letter='c': backtrack(index=1, current="c")
       -> letter='d': append "cd"
       -> letter='e': append "ce"
       -> letter='f': append "cf"

result = ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Base case kích hoạt đúng tại index == len(digits). Không có việc duy trì kết quả partial, không có list đang lớn để cập nhật giữa chừng. Mỗi lá của cây recursion giữ một câu trả lời hoàn chỉnh.

Các edge case đáng phân tích

Input rỗng (digits = ""). Cả hai approach kiểm tra ở đầu và trả về []. Nếu bỏ qua guard này, approach lặp trả về [''] (seed) — sai theo đề bài — còn backtracking trả về đúng [] vì backtrack(0, "") ngay lập tức đạt index == 0 == len("") và append chuỗi rỗng. Vì vậy guard chuỗi rỗng là cần thiết cho approach lặp, hơi dư thừa nhưng làm rõ ý định cho backtracking.

Một chữ số (digits = "2"). Lặp: seed [''] được mở rộng thành ['a','b','c'], đúng. Backtracking: ba lần gọi lá, mỗi cái sâu một ký tự. Cả hai cho ["a","b","c"].

Chữ số '7' hoặc '9' (bốn chữ cái mỗi cái). Đây là chỗ duy nhất mà bound 4^n chặt hơn 3^n. digits = "7777" cho 4^4 = 256 kết quả độ dài 4. Ánh xạ {'7': 'pqrs', '9': 'wxyz'} xử lý điều này — chỉ cần xác nhận bạn không gõ nhầm thành chuỗi ba chữ cái cho hai chữ số đó.

Tất cả cùng chữ số (digits = "9999"). Cho 256 chuỗi bốn ký tự từ {w,x,y,z}^4. Cả hai approach xử lý giống hệt nhau; không có gì khác biệt về cấu trúc với chữ số lặp lại.

Độ dài tối đa (digits.length = 4). Với tất cả chữ số là '7' hoặc '9', bạn có 256 chuỗi output. Với tất cả là key ba chữ cái, bạn có 3^4 = 81. Trong cả hai trường hợp đây là hằng số nhỏ — constraint digits.length <= 4 rõ ràng được chọn để đảm bảo điều này.

Bảng so sánh

Time bound giống hệt nhau. Câu chuyện về space khác nhau: lặp giữ hai list đầy đủ đồng thời trong mỗi bước mở rộng (cũ và mới). Backtracking giữ một call stack sâu n và tích lũy kết quả chỉ tại các lá.

Với n <= 4 và tối đa 256 kết quả, không approach nào gây ra vấn đề tài nguyên. Đây là lựa chọn về tính đúng đắn và sự rõ ràng, không phải hiệu suất.

Tôi sẽ ship cái nào và tại sao

Tôi chọn phiên bản backtracking ngay lập tức. Không phải vì sự khác biệt allocation stack vs heap — với n = 4 điều đó không thực sự quan trọng. Mà vì code backtracking là bản dịch trực tiếp của cách bạn nghĩ về bài toán: chọn một chữ cái, đi sâu hơn, quay lại, thử chữ cái tiếp theo. Phiên bản lặp đòi bạn ghi nhớ trong đầu rằng result là "mọi tổ hợp của prefix đến nay" — một invariant đúng nhưng ít tự nhiên hơn.

Lý do khác: backtracking scale tốt với các biến thể có ràng buộc của bài này theo cách mà lặp không làm được. Nếu bạn thêm điều kiện ("chỉ các tổ hợp không lặp cùng chữ cái liên tiếp") hoặc quy tắc pruning, bạn đặt nó vào hàm backtrack và nó hoạt động ngay. Với approach lặp bạn phải tái cấu trúc logic vòng ngoài.

Vị trí trong series backtracking

Đây là bài thứ 8 trong series, sau Subsets, Permutations, Combination Sum và các biến thể. Những bài đó liên quan đến việc chọn phần tử từ một collection duy nhất. Letter Combinations có cấu trúc khác: bạn có một nhóm lựa chọn cho mỗi vị trí (digits[i] -> chữ cái), và các nhóm có kích thước và nội dung khác nhau. Đó là ý tưởng mới ở đây — cây quyết định không đối xứng. Mỗi level phân nhánh khác nhau tùy thuộc vào chữ số bạn đang xét.

Pattern cơ bản vẫn như cũ: tại mỗi node trong search tree, liệt kê tất cả lựa chọn, recurse, undo. Điều thay đổi là cách định nghĩa các lựa chọn.

Generate Parentheses (22) là bài đồng hành tự nhiên: lựa chọn ở mỗi bước bị ràng buộc bởi quy tắc hợp lệ (bạn chỉ có thể đóng ngoặc nếu số ngoặc mở cho phép), không phải bởi một map bên ngoài. Backtracking với pruning, không phải backtracking với lookup.

Combination Sum (39) cho phép bạn chọn từ cùng một collection nhiều lần. Branching factor đồng đều qua các level. Letter Combinations có branching không đồng đều — ba chữ cái cho một số chữ số, bốn cho số khác — nhưng không có lựa chọn lặp.

Permutations (46) có alphabet cố định và tất cả lựa chọn ở mọi level, nhưng không thể tái sử dụng một phần tử ở cùng vị trí. Constraint khác, cùng DFS skeleton.

Word Search (79) mở rộng ý tưởng theo không gian: thay vì chọn từ map, bạn chọn từ các ô lân cận trên lưới. Skeleton backtracking không đổi; chỉ có định nghĩa "lựa chọn hợp lệ tiếp theo" là khác.