A 0ms C++ backtracking solution


  • 0
    H
    class Solution {
    protected:
        vector<string> comb;
        vector<vector<char>> dict;
    public:
        vector<string> letterCombinations(string digits) {
            string prefix = string();
            dict = vector<vector<char>>(10, vector<char>());
            dict[2] = vector<char>({'a', 'b', 'c'});
            dict[3] = vector<char>({'d', 'e', 'f'});
            dict[4] = vector<char>({'g', 'h', 'i'});
            dict[5] = vector<char>({'j', 'k', 'l'});
            dict[6] = vector<char>({'m','n','o'});
            dict[7] = vector<char>({'p', 'q', 'r', 's'});
            dict[8] = vector<char>({'t', 'u', 'v'});
            dict[9] = vector<char>({'w', 'x', 'y', 'z'});
            combine(prefix, digits);
            return comb;
        }
        
        void combine(string& prefix, string digits) {
            int d = int(digits[0] - '0');
            if (digits.length() == 0 and prefix.length() > 0) 
                comb.push_back(prefix);
            else {
                if (-1 < d && d < 10) {
                    for (int i = 0; i < dict[d].size(); i++) {
                        prefix.push_back(dict[d][i]);
                        combine(prefix, digits.substr(1));
                        prefix.pop_back();
                    }
                }            
            }
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.