17. Letter Combinations of a Phone Number
Tags:
Medium
Skills:
backtrack
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 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
Time and space complexity
Solution
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};