0ms c++ solution using recursion


  • 0
    L

    Similar thought with Subset and Subset II and so on.

    class Solution {
    public:
        int LetterNum(char digit){
            if(digit == '9' || digit == '7')
                return 4;
            return 3;
        }
        bool helper(char lookup[8][4], string& digits, int start, 
                                vector<string>& ret, string& go)
        {
            if(start >= digits.size())
                return true;
            if(digits[start] == '1') // if the digits string include '1', we will finally return an empty vector<string>
                return false;
            int width = LetterNum(digits[start]); // calculate one digit's lookup table size
            for(int i = 0; i < width; i++)
            {
                go += lookup[digits[start]-0x32][i];
                if(go.size() == digits.size())
                	ret.push_back(go);
                else
                	if(!helper(lookup, digits, start+1, ret, go))
                		return false;
                go.pop_back();
            }
            return true;
        }
        
        vector<string> letterCombinations(string digits) {
            vector<string> ret;
            if(digits.size() == 0)
                return ret;
            // build a lookup table;
            char table[8][4] = {{'a','b','c'}, {'d','e','f'},{'g','h','i'}, {'j','k','l'},
                {'m','n','o'}, {'p','q','r','s'}, {'t','u','v'}, {'w','x','y','z'}};
            string go;
            if(helper(table, digits, 0, ret, go))
                return ret;
            return vector<string>();
        }
    };

Log in to reply
 

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