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.
思路：第一眼看到这道题觉得不难，只需要利用for循环暴力寻找所有的组合结果就可以了，但是仔细一想发现，我们事先不知道digits的大小，于是就无法确定使用for循环的层数。怎么办呢？嗯，可以用递归来代替for循环。那么递归我们要递归什么呢？当然是要递归digits中的数字啦，然后对每个数字对应的字符进行遍历，来组合所有的可能。
class Solution { public: vector<string> letterCombinations(string digits) { vector<string> letter; if (digits.empty()) return letter; vector<string> num = { "abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" }; string let; dfs(digits, letter, let, 0, num); return letter; } void dfs(string& digits, vector<string>& letter, string& let, int pos, vector<string> num) { if (pos == digits.size()) { letter.push_back(let); return; } int x = (digits[pos] - '0') - 2; string s = num[x]; for (int i = 0; i < s.size();i++) { let.push_back(s[i]); dfs(digits, letter, let, pos + 1, num); let.pop_back(); } } };
