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解决
class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string>ans;
dfs(digits,0,"",ans);
return ans;
}
void dfs(string digits, int start, string s, vector<string>&ans){
if(start == digits.size()){
if(s != "")
ans.push_back(s); return;
}
int cnt = digits[start]-'2';
for(int i = 0; i < 4; i++)
if(letter[cnt][i] != '!')
dfs(digits, start+1,s+letter[cnt][i],ans);
}
char letter[8][4] = {
{'a', 'b', 'c', '!'},
{'d', 'e', 'f', '!'},
{'g', 'h', 'i', '!'},
{'j', 'k', 'l', '!'},
{'m', 'n', 'o', '!'},
{'p', 'q', 'r', 's'},
{'t', 'u', 'v', '!'},
{'w', 'x', 'y', 'z'}
};
};