[0017] 电话号码的字母组合
- GitHub
- http://leetcode.xuezhisd.top/post/d7048d6c.html
- https://leetcode.com/problems/letter-combinations-of-a-phone-number
- https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
题目描述
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入："23" 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
Related Topics
题目解析
- 本题是一个搜索题，可以用dfs和bfs解决
不确定性
- 需要确定输入字符串最大长度
- 长度是否可以为0
方法一：dfs
分析
- 利用模拟法可以知道对于给定的字符，每一位上选择一个字母，所有的组合就是答案
- 模拟如下：
| char | 2 | 3 | 结果 |
|---|---|---|---|
| 选项1 | a | d | ad, ae, af |
| 选项2 | b | e | bd, be, bf |
| 选项3 | c | f | cd, ce, cf |
思路
伪代码框架如下：
```go
dfs(dep, num, result)
{
if dep==len(num) : return // 选择完毕
for c in charSet[num[dep]] // 在本层枚举每一种可能
{dfs(dep+1, num, result+c)}
}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
37
38
39
40
41
42
43
44
45
46
47
- 输入长度为0
- 暴力
- dfs
- 组合
- 空间复杂度O(n)
- 时间复杂度O(2^n)
```cpp
class Solution {
const string CharSet[10] = {"","","abc","def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
void dfs(int dep, string &digits, string tmp, vector<string> &result)
{
if(dep == digits.length())
{
if (tmp!="")result.push_back(tmp); // digit为空
return;
}
for(char c : CharSet[digits[dep]-'0'])
{
dfs(dep+1, digits, tmp+c, result);
}
}
public:
vector<string> letterCombinations(string digits) {
vector<string> res;
dfs(0, digits, "", res);
return res;
}
};
/*
""
"234"
"2233"
"23456789"
*/
方法二：bfs
分析
- 与dfs不同的是，bfs是每次都会列出所有可能。
| char | 2 | 3 |
|---|---|---|
| 选项1 | a | ad, ae, af |
| 选项2 | b | bd, be, bf |
| 选项3 | c | cd, ce, cf |
思路
伪代码框架如下：
```go
bfs(num)
{
que = [“”]
step = 0
while(!q.empty)
{if step>=len(num): break l = len(q) while(l--) { f = que.front() que.pop() for c in charSet[num[step]] // 在本层枚举每一种可能 { que.push(f+c) } } step++}
return que // que中所有元素即为结果
}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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#### 注意
- 输入长度为0
#### 知识点
- bfs广度优先遍历
- 暴力
- 组合
#### 复杂度
- 空间复杂度O(2^n)
- 时间复杂度O(2^n)
#### 代码
```cpp
class Solution {
const string CharSet[10] = {"","","abc","def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
vector<string> bfs(string digits)
{
if (0== digits.length()) return vector<string>();
queue<string> q;
q.push("");
int step=0;
while(!q.empty())
{
if (step >= digits.length())break; // 所有都选择完毕了
int l = q.size();
while(l--) {
auto f = q.front();
q.pop();
for (auto c : CharSet[digits[step] - '0']) {
q.push(f + c);
}
}
step++;
}
vector<string> res;
while(!q.empty())
{
res.push_back(q.front());
q.pop();
}
return res;
}
public:
vector<string> letterCombinations(string digits) {
return bfs(digits);
}
};
/*
""
"23"
"234"
"2233"
"23456789"
*/