17. 电话号码的字母组合

Reference

代码随想录 (programmercarl.com)

Problem: 17. 电话号码的字母组合

思路

同样的回溯暴力搜索，需要注意的我们每次取的是
string letters = map[digits[index]- '0'];
下一个字母的组合。

for(int i = 0; i < letters.size(); i++)
循环中遍历的是下一个字母组合中的每一个字母

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]

class Solution {
public:
    const string map[10] = {
        "",
        "",
        "abc",//2
        "def",//3
        "ghi",//4
        "jkl",//5
        "mno",//6
        "pqrs",//7
        "tuv",//8
        "wxyz"//9
    };
    vector<string> res;
    string path;
    void backTracing(string digits,int index) {
        if(path.size() == digits.size()) {
            res.push_back(path);
            return;
        }
        string letters = map[digits[index]- '0'];
        for(int i = 0; i < letters.size(); i++) {
            char letter = letters[i];
            path.push_back(letter);
            backTracing(digits,index+1);
            path.pop_back();
        }
    } 
    vector<string> letterCombinations(string digits) {
        if(digits == "") return res;
        backTracing(digits,0);
        return res;
    }
};