回溯

将 222——999 和字母对应起来，用字符串数组保存。

递归遍历 digitsdigitsdigits 每一个数字，每一个数字对应的字母，又可以递归遍历，和下一个数字的字母组成排列。当排列长度等于 digitsdigitsdigits 的长度，就组成了一个排列。

dfsdfsdfs 树 ， 以 digits=2/3/4digits = 2/3/4digits=2/3/4 为例

只画出了部分 dfsdfsdfs 树，bbb 和 ccc 的子树可以参考 aaa ，一共 33=273^3=2733=27 种组合。

代码展示

class Solution {
public:string strs[10]{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz",};vector ans ;vector letterCombinations(string digits) {//回溯法if(digits.empty()) return ans;//输入空，返回空。dfs(digits,0,"");return ans;}void dfs(string digits, int u , string path){//u在path对应第几个字符。if(u==digits.size()) ans.push_back(path);else{for(char &x:strs[digits[u]-'0'])//u在digits对应第几个数字。dfs(digits,u+1,path+x);}}
};

博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC

复杂度分析

1. 时间复杂度: O(4n×n)O(4^n\times n )O(4n×n)， nnn 是 digitsdigitsdigits 的长度 ， 每个数字最多对应 444 个字母 ， 递归组合，最坏时间复杂度O(4n)O(4^n)O(4n)，push_backpush\_backpush_back 的时间复杂度 O(n)O(n)O(n) ，综上，最坏时间复杂度O(4n)O(4^n)O(4n)。
2. 空间复杂度: O(n)O(n)O(n)，压栈最大深度 nnn ，对应的空间复杂度 O(n)O(n)O(n) 。