0ms recursive solution using c++


  • 0
    J
    class Solution {
        unordered_map<char, vector<char>> digit_letter;
        void init_map(){
            char start = 'a';
            int offset = 0;
            for(int i = 2; i <= 9; i++){
                vector<char> val;
                if(i == 7 || i == 9)
                    for(int j = 0; j < 4; j++)
                        val.push_back(start + offset++);
                else
                    for(int j = 0; j < 3; j++)
                        val.push_back(start + offset++);
                string key = to_string(i);
                digit_letter[key[0]] = val;
            }
        }
    public:
        vector<string> letterCombinations(string digits) {
            vector<string> ret;
            if(digits.length() == 0)
                return ret;
            init_map();
            
            return helper(digits.length() - 1, digits);
        }
        
        vector<string> helper(int i, string digits){
            vector<string> ret;
            if(i == 0){
                vector<char> temp = digit_letter[digits[0]];
                for(auto c: temp)
                    ret.push_back(string(1, c));
                return ret;
            }else{
                vector<string> temp = helper(i - 1, digits);
                for(auto c: digit_letter[digits[i]])
                    for(auto s: temp)
                        ret.push_back(s + c);
                return ret;
            }
        }
    };
    

    just to combine string from start to end


  • 0
    P

    I like your method.

    most people like bottom-up, and you give a top-down solution.


Log in to reply
 

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