17. 电话号码的字母组合

1.题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

2.思路

当给定了输入字符串，比如：“23”，那么整棵树就构建完成了，如下：

问题转化成了从根节点到空节点一共有多少条路径；

3.代码

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> res;
        if(digits.empty()){
            return res;
        }
        string str;
        findCombinations(digits,0,str,res);
        return res;
    }
    void findCombinations(string& digits,int i,string& str, vector<string>& res){
        if(i == digits.size()){
            res.push_back(str);
            return;
        }
        char digit = digits[i];//选择第i个数字
        string letters = digits_map[digit-'0'];
        for(auto &w : letters){
            str += w;
            findCombinations(digits, i+1,str,res);
            str.pop_back();
        }
        return;
    }
private:
    vector<string> digits_map = {
            " ",    //0
            "",     //1
            "abc",  //2
            "def",  //3
            "ghi",  //4
            "jkl",  //5
            "mno",  //6
            "pqrs", //7
            "tuv",  //8
            "wxyz"  //9
    };
};

4.复杂度分析

时间复杂度：$O(3^N × 4^M)$O(3N×4M)，$N$N 为电话号码中拥有 3 个字母的按键个数，$M$M为电话号码中拥有 4 个字母的按键个数。
空间复杂度：$O(3^N × 4^M)$O(3N×4M)，同上。