17. Letter Combinations of a Phone Number

Problem

Bài toán yêu cầu liệt kê tất cả các tổ hợp chữ cái có thê tạo thành từ một chuôi số (chỉ gồm các số từ 2→9), dựa trên bảng chữ cái của bàn phím điện thoại cổ điển. Đây là bài toán tổ hợp điển hình, thích hợp giải bằng phương pháp đệ quy (backtracking) hoặc duyệt theo chiều sâu DFS

Approach

Tạo một ánh xạ từ số sang các chữ cái tương ứng

Nếu chuỗi đầu vào rỗng, return về mảng rông

Sử dụng đệ quy để xây dựng dần các tổ hợp, mỗi bước duyệt qua từng chữ cái ứng với số hiện tại và tiếp tục với số tiếp theo

Khi đã xây dụng đủ độ dài tổ hợp (bằng độ dài chuỗi đầu vào), thêm tổ hợp vào kết quả

Time and space complexity

TC: O(n * 4^n)

SC: O(n * 4^n)

n là độ dài chuỗi digits

Mỗi chữ số có tối đa 4 chữ cái

Số tổ hợp tối đa 4^n (vì mỗi vị trí có tối đa 4 lựa chọn)

Với mỗi tổ hợp, việc xây dựng chuỗi kết quả có độ dài n

Solution

typescripttypescript

1function letterCombinations(digits: string): string[] {
2    const map: { [key: string]: string } = {
3        '2': 'abc',
4        '3': 'def',
5        '4': 'ghi',
6        '5': 'jkl',
7        '6': 'mno',
8        '7': 'pqrs',
9        '8': 'tuv',
10        '9': 'wxyz'
11    };
12    if (digits.length === 0) return [];
13    const res: string[] = [];
14    function backtrack(idx: number, path: string): void {
15        if (idx === digits.length) {
16            res.push(path);
17            return;
18        };
19        const letter = map[digits[idx]];
20        for (const char of letter) backtrack(idx + 1, path + char)
21        return;
22    }
23    backtrack(0, '')
24    return res;
25};

Loading content...