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.
每个数字代表一个种类，每个种类中有多个值，要求在每个种类中都选一个，所组成的所有不同的组合。
class Solution {
public:
void dfs(vector<string>& re, int cur_dep,string& cur_re, string digits){
static string tel_board[] = {
"0", "1", "abc", "def", "ghi",
"jkl", "mno", "pqrs", "tuv", "wxyz", };
if(cur_dep == digits.length()){
re.push_back(cur_re);
return;
}
string cur_str = tel_board[digits[cur_dep] - ‘0‘];
for (int i = 0; i < cur_str.length(); ++i)
{
cur_re.push_back(cur_str[i]);
dfs(re, cur_dep + 1, cur_re, digits);
cur_re.pop_back();
}
}
vector<string> letterCombinations(string digits) {
vector<string> re;
string cur_re("");
dfs(re, 0, cur_re, digits);
return re;
}
};
注：做完这些题，总结dfs的特点，以及求解dfs的套路。