17.电话号码的字母组合
给定一个仅包含数字 2-9 的字符串 digits，返回所有它能表示的字母组合（数字到字母的映射与电话按键相同）。例如
输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
通过分析样例可以发现，结果类似于笛卡尔积，即全排列。由于输入数组的长度不固定，因此采用搜索与回溯的方法进行求解。
算法实现步骤如下：
- 使用 unordered_map 建立数字与字母的映射关系
- 遍历 digits 的每个位置，在映射表中查找对应的字母，通过递归方式构建结果字符串，直到结果字符串的长度与 digits 的长度相等为止
代码：
class Solution {
public:vector<string> ans;unordered_map<int,string> mp = {{0," "},{1," "},{2,"abc"},{3,"def"},{4,"ghi"},{5,"jkl"},{6,"mno"},{7,"pqrs"},{8,"tuv"},{9,"wxyz"}};void dfs(int i,int n,string& digits,string& temp,unordered_map<int,string> &mp) {if (i == n) {ans.emplace_back(temp);return;}for (char c:mp[digits[i] - '0']) {temp[i] = c;dfs(i + 1,n,digits,temp,mp);}}vector<string> letterCombinations(string digits) {if (digits.size() == 0) return ans;int n = digits.size();string temp(n,0);dfs(0,n,digits,temp,mp);return ans;}
}; 
时间复杂度：O(n*4^n)，n为digits长度，每个数字最多对应4个字母，树高为n，叶子节点树为4^n，每个节点需要O(n)时间构造字符串，共O(n*4^n)
空间复杂度：O(n),递归最多n次，栈需要O(n)，temp长度O(n)