mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
79 lines
2.5 KiB
Markdown
79 lines
2.5 KiB
Markdown
# [17. Letter Combinations of a Phone Number](https://leetcode.com/problems/letter-combinations-of-a-phone-number/)
|
||
# 思路
|
||
## 思路一
|
||
举例说明吧。
|
||
1. `digits = "2"`时，结果显然是`res = ["a","b","c"]`；
|
||
2. `digits = "23"`时，1中res的每一个字符串后都可以接d、e、f任意一个，所以可以先将1中的res中所有元素复制两遍
|
||
变成["a","b","c","a","b","c","a","b","c"]，再在此时res的每一个元素后面合适地接上d、e、f其中一个就变成了
|
||
["ad","bd","cd","ae","be","ce","af","bf","cf"]。
|
||
|
||
由此就可以写出代码了。
|
||
时间复杂度O(n^2)，空间复杂度O(1)
|
||
|
||
## 思路二
|
||
其实可以将此题看成求解一棵树的所有root(root可以看做是空)到叶子的路径。
|
||
例如当`digits = "23"`时，树应该是这个样子:
|
||
```
|
||
root
|
||
/ | \
|
||
2: a b c
|
||
/|\ /|\ /|\
|
||
3: def def def
|
||
```
|
||
所以就可以用DFS求解这题了。
|
||
|
||
|
||
# C++
|
||
## 思路一
|
||
```C++
|
||
class Solution {
|
||
public:
|
||
vector<string> letterCombinations(string digits) {
|
||
int len = digits.size();
|
||
vector<string>res;
|
||
if(len == 0) return res;
|
||
|
||
const vector<string>digit2char{"","","abc","def","ghi",
|
||
"jkl","mno","pqrs","tuv","wxyz"};
|
||
res.push_back("");
|
||
for(int i = 0; i < len; i++){
|
||
int digit = int(digits[i] - '0');
|
||
int curr_res_size = res.size();
|
||
for(int k = 0; k < digit2char[digit].size() - 1; k++) // 将res中所有元素复制几遍
|
||
for(int j = 0; j < curr_res_size; j++)
|
||
res.push_back(res[j]);
|
||
for(int k = 0; k < digit2char[digit].size(); k++)
|
||
for(int j = 0; j < curr_res_size; j++)
|
||
res[k * curr_res_size + j] += digit2char[digit][k];
|
||
}
|
||
return res;
|
||
|
||
}
|
||
};
|
||
```
|
||
|
||
## 思路二
|
||
``` C++
|
||
class Solution {
|
||
private:
|
||
const vector<string>digit2char{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
|
||
void DFS(const string &digits, string out, vector<string> &res){
|
||
int start = out.size();
|
||
if(start == digits.size()){
|
||
res.push_back(out);
|
||
return;
|
||
}
|
||
for(char c: digit2char[digits[start]-'0'])
|
||
DFS(digits, out+c, res);
|
||
}
|
||
public:
|
||
vector<string> letterCombinations(string digits) {
|
||
vector<string>res;
|
||
if(digits.size() == 0) return res;
|
||
string out;
|
||
DFS(digits, out, res);
|
||
return res;
|
||
}
|
||
};
|
||
```
|