电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
示例 2：

输入：digits = “”
输出：[]
示例 3：

输入：digits = “2”
输出：[“a”,“b”,“c”]

提示：

0 <= digits.length <= 4
digits[i] 是范围 [‘2’, ‘9’] 的一个数字。

使用一个向量作为哈希表，存键盘数字到对应可选字符的映射关系。

题解：
如果输入为空不用处理。
深度优先搜索到末尾数字结束。
对应每个数字，往所有可能的分支（字符）进行深度优先搜索。

代码：

vector<string> a{ "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
string b;class Solution {
public:vector<string> ans;void dfs(int n, string digits){if (n == digits.size()){ans.push_back(b);return;}for (int i = 0; i < a[digits[n]-'0'].size(); i++){b.push_back(a[digits[n] - '0'][i]);dfs(n + 1, digits);b.pop_back();}}vector<string> letterCombinations(string digits) {if(digits.size()==0) return {};dfs(0, digits);return ans;}
};

时间复杂度：O(n4n)O(n4^n)O(n4
n
)，其中 nnn 为 digits\\textit{digits}digits 的长度。最坏情况下每次需要枚举 444 个字母，递归次数为一个满四叉树的节点个数，那么一共会递归 O(4n)O(4^n)O(4
n
) 次（等比数列和），再算上加入答案时需要 O(n)O(n)O(n) 的时间，所以时间复杂度为 O(n4n)O(n4^n)O(n4
n
)。
空间复杂度：O(n)。返回值的空间不计。