# [leetcode] Letter Combinations of a Phone Number

### 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"].
```

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

tag: backtracking, string

```class Solution {
public:
vector<string> data;
vector<string> letterCombinations(string digits){
data.push_back("");//0
data.push_back("");//1
data.push_back("abc");//2
data.push_back("def");//3
data.push_back("ghi");//4
data.push_back("jkl");//5
data.push_back("mno");//6
data.push_back("pqrs");//7
data.push_back("tuv");//8
data.push_back("wxyz");//9
return _letterCombinations(digits);
}
vector<string> _letterCombinations(string digits) {
if (digits.size() == 0){
vector<string> re;
re.push_back("");
return re;
}
if (digits.size() == 1){
vector<string> re;
char c = digits[0];
for(int i = 0; i < data[c - '0'].size(); i++){
string s;
s.push_back(data[c - '0'][i]);
re.push_back(s);
}
return re;
}
else{//size > 1
vector<string> re;
vector<string> lastRe = _letterCombinations(digits.substr(1));
char c = digits[0];
for(int i = 0; i < data[c - '0'].size(); i++){
for(int j = 0; j < lastRe.size(); j++){
re.push_back(data[c - '0'][i] + lastRe[j]);
}
}
return re;
}
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.