题目

题解

  • 时间复杂度$O(3^{N}+4^{M})$，N是有三个字母的数字数量，M是有4个字母的数字数量。
  • 空间复杂度$O(3^{N}+4^{M})$,保存结果的数量
class Solution {
        vector<string> res;//定义res保存结果
public:
    vector<string> letterCombinations(string digits) {
        if(digits.empty()) return res;//digits为0，返回空res
        vector<string> dict = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};//定义数字对应的数组，0，1为空
        getLettersDFS(digits,dict,0,"");//调用递归函数
        return res;//返回结果
    }

    void getLettersDFS(const string& digits,const vector<string>& dict, int level, string out){
        if(level == digits.size()){
            res.push_back(out);
            return;
        }//若level等于digits的长度，说明level已经遍历完所有的字符，（level从0开始到digits.size()-1），则把暂存的结果out加入res
        string str = dict[digits[level] - '0'];//将第level-1个数多代表的几个字母存入str
        for(int i=0; i<str.size(); i++){
            getLettersDFS(digits, dict, level+1, out+str[i]);//遍历str中的所有字母，加到out后面并递归
        }
    }
};