coding
unsky
deepdim
thought

Letter Combinations of a Phone Number

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”].

问题可以归结为backtracking问题,使用递归,需要建立对应得字母表

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
class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string> res;
if (digits.length()==0)
return res;
string dict[] = {" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
string comb(digits.length(),'/0');
backtracking(digits,res,dict,comb,0);
return res;
}
void backtracking(string digits,vector<string> &res,string dict[],string &comb, int index)
{ if(index==digits.size())
{res.push_back(comb);
return;
}
string str=dict[digits[index]-'0'];
for(int i=0;i<str.length();i++)
{comb[index]=str[i];
backtracking(digits,res,dict,comb,index+1);
}
}
};

坚持原创技术分享,您的支持将鼓励我继续创作!