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

题目描述

思路及解法

1.将电话号码和对应的数组存入数组中创建映射关系；
2.编写，并调用回溯函数，当决策阶段等于digits的长度时，将当前的决策路径添加到结果集合中，否则从digits字符串的第一个字符开始回溯调用！我们在回溯时利用一个变量记录决策阶段，每次取出对应决策阶段可能的字母，并在此阶段上回溯

复杂度

时间复杂度:

最坏时间复杂度：$O(3^m\times 4^n)$,其中m表示选择对应只有三个字母的数字的个数，n表示对应四个字母的个数

空间复杂度:

$O(n+m)$

Code

class Solution {
    //Recode the result
    vector<string> res;
    //Recode the decision path
    vector<char> track;
public:
    /**
     * Get the all possible combinations
     *
     * @param digits The combination given by topic
     * @return vector<string>
     */
    vector<string> letterCombinations(string digits) {
        if (digits.size() == 0) {
            return {};
        }
        //Create the reflection
        vector<string> mappings(10);
        mappings[2] = "abc";
        mappings[3] = "def";
        mappings[4] = "ghi";
        mappings[5] = "jkl";
        mappings[6] = "mno";
        mappings[7] = "pqrs";
        mappings[8] = "tuv";
        mappings[9] = "wxyz";
        backtrack(mappings, digits, 0, track);
        return res;
    }

    /**
     * Use backtracking to find all possible combinations
     *
     * @param mappings Mapping between letters and numbers
     * @param digits Combination of numbers given by topic
     * @param stage Decision stage
     * @param track Decision path
     */
    void backtrack(vector<string> &mappings, string &digits, int stage, vector<char> &track) {
        //End condition
        if (stage == digits.length()) {
            res.push_back(string(track.begin(), track.end()));
            return;
        }
        string mapping = mappings[digits[stage] - '0'];
        for (int i = 0; i < mapping.length(); ++i) {
            track.push_back(mapping[i]);
            backtrack(mappings, digits, stage + 1, track);
            track.pop_back();
        }
    }
};