Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.
Input:Digit string "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
dfs递归解法
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class
Solution {
public
:
vector<string> letterCombinations(string digits) {
vector<string> res;
string tmpres(digits.size(),
' '
);
dfs(digits, 0, tmpres, res);
return
res;
}
void
dfs(
const
string &digits,
int
index, string &tmpres, vector<string>&res)
{
string numap[] = {
" "
,
""
,
"abc"
,
"def"
,
"ghi"
,
"jkl"
,
"mno"
,
"pqrs"
,
"tuv"
,
"wxyz"
};
if
(index == digits.size())
{
res.push_back(tmpres);
return
;
}
for
(
int
i = 0; i < numap[digits[index] -
'0'
].size(); i++)
{
tmpres[index] = numap[digits[index] -
'0'
][i];
dfs(digits, index+1, tmpres, res);
}
}
};
|
根据编程之美-3.2电话号码对应英语单词 中的代码3-4，我们有如下的非递归解法，其实是把上述递归改为非递归
1 class Solution { 2 public: 3 vector<string> letterCombinations(string digits) { 4 vector<string>res; 5 vector<int> ansIndex(digits.size(), 0); 6 string numap[] = {" ","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; 7 8 while(true) 9 { 10 string tmp(digits.size(),' '); 11 for(int i = 0; i < digits.size(); i++) 12 tmp[i] = numap[digits[i]-'0'][ansIndex[i]]; 13 res.push_back(tmp); 14 int k = digits.size() - 1; 15 while(k >= 0) 16 { 17 if(ansIndex[k] < numap[digits[k]-'0'].size() - 1) 18 { 19 ansIndex[k]++; 20 break; 21 } 22 else 23 { 24 ansIndex[k] = 0; 25 k--; 26 } 27 } 28 if(k < 0)break; 29 } 30 31 return res; 32 } 33 };
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class
Solution {
public
:
vector<string> letterCombinations(string digits) {
vector<string> res(1,
""
);
string numap[] = {
" "
,
""
,
"abc"
,
"def"
,
"ghi"
,
"jkl"
,
"mno"
,
"pqrs"
,
"tuv"
,
"wxyz"
};
for
(
int
i = 0; i < digits.size(); i++)
{
vector<string>tmp;
for
(
int
j = 0; j < res.size(); j++)
for
(
int
k = 0; k < numap[digits[i] -
'0'
].size(); k++)
tmp.push_back(res[j] + numap[digits[i] -
'0'
][k]);
res = tmp;
}
return
res;
}
};
|
本文转自tenos博客园博客，原文链接：http://www.cnblogs.com/TenosDoIt/p/3771254.html，如需转载请自行联系原作者
