题目：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例: 输入：“23” 输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”]. 说明: 尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
class Solution { public: vector<string> letterCombinations(string digits) { if(digits.empty()) return {}; vector<vector<char>> d(10); d[0] = {' '}; d[1] = {}; d[2] = {'a', 'b', 'c'}; d[3] = {'d', 'e', 'f'}; d[4] = {'g', 'h', 'i'}; d[5] = {'j', 'k', 'l'}; d[6] = {'m', 'n', 'o'}; d[7] = {'p', 'q', 'r', 's'}; d[8] = {'t', 'u', 'v'}; d[9] = {'w', 'x', 'y', 'z'}; vector<string> ans{""}; for(char digit : digits) { vector<string> tmp; for(const string& s : ans) { for(char c : d[digit - '0']) { tmp.push_back(s+c); } } ans.swap(tmp); } return ans; } };时间复杂度：O(4^n) 空间复杂度：O(〖2×4〗^n)
DFS：
class Solution { public: vector<string> letterCombinations(string digits) { if(digits.empty()) return {}; vector<vector<char>> d(10); d[0] = {' '}; d[1] = {}; d[2] = {'a', 'b', 'c'}; d[3] = {'d', 'e', 'f'}; d[4] = {'g', 'h', 'i'}; d[5] = {'j', 'k', 'l'}; d[6] = {'m', 'n', 'o'}; d[7] = {'p', 'q', 'r', 's'}; d[8] = {'t', 'u', 'v'}; d[9] = {'w', 'x', 'y', 'z'}; //cur存储中间结果 string cur; //ans存储最终答案 vector<string> ans; dfs(digits, d, 0, cur, ans); return ans; } private: //dfs遍历所有答案 void dfs(const string& digits, const vector<vector<char>>& d, int l, string& cur, vector<string>& ans) { //递归的结束条件 if( l == digits.length()) { //当前递归结束时，将结果存入ans，并返回 ans.push_back(cur); return; } //for循环遍历当前数字中的字母 for(const char c: d[digits[l] - '0']) { cur.push_back(c); dfs(digits,d,l+1,cur,ans); //一次深度优先搜索完成时，删除cur中元素以便进行回溯 cur.pop_back(); } } };时间复杂度：O(4^n) n为输入的长度 空间复杂度：O(4^n+n)
[[C++]Leetcode超高效刷题顺序及题目详解笔记（持续更新中）]
