算法内容
本文件实现 LeetCode 17「电话号码的字母组合」。问题要求根据数字到字母的映射，生成所有可能的字符串组合。
代码维护数字串、长度、结果数组和映射表，通过回溯函数 search(depth, s) 逐位枚举当前数字对应的所有字符。当 depth == len 时，说明已经构造出一个完整组合，将其加入结果。若输入为空字符串，直接返回空结果。时间复杂度与组合数量成正比，约为 O(3^m * 4^n)，其中 m/n 分别是映射到 3 个/4 个字母的数字数量。
算法实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#include<vector>
#include<iostream>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;
class Solution {
public:
string digits;
int len;
vector<string> res;
vector<string> table;
vector<string> letterCombinations(string digits) {
this->digits = digits;
this->len = digits.length();
table = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
if(digits == "") return res;
search(0, "");
return res;
}
void search(int depth, string s) {
if(depth == len) {
res.push_back(s);
return;
}
char c = digits[depth] - '2';
int len = (c == '7'-'2' || c == '9'-'2') ? 4 : 3;
for(int i = 0; i < len; i++) {
search(depth+1, s+table[c][i]);
}
}
};
|