My C++ recursive DFS+Backtracking solution & another iterative solution


  • 1
    D

    The recursive solution scan the input number string from left to right via dfs+backtracking.

    // assume all the digits are in [2, 9]
    class Solution {
    private:
        void dfsHelper(vector<string> &res, string &cur, vector<string> &map, int start, int sLen, const string &digits)
        {
            if(start == sLen) res.push_back(cur); // if reaching the end, push cur to res
            else
            {
                cur.push_back('0'); // add one new character. '0' is just a place holder
                for(auto i:map[digits[start]-'0']) // go through each possible charactor
                {
                    cur.back() = i; // set the new character value
                    dfsHelper(res, cur, map, start+1, sLen, digits); // do dfs
                }
                cur.pop_back(); // backtracking
            }
        }
    
    public:
        vector<string> letterCombinations(string digits) {
            vector<string> res;
            vector<string> map = {"", "", "abc", "def","ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
            string cur;
            int sLen = digits.size();
            
            if(sLen) dfsHelper(res, cur, map, 0, sLen, digits);
            
            return res;
        
        }
    };
    

    It is easy to change the above solution into an iterative one, one example given as below

    // assume all the digits are in [2, 9]
    class Solution {
    public:
        vector<string> letterCombinations(string digits) {
            vector<string> res;
            const vector<string> map = {"", "", "abc", "def","ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
            int  resSize,i, sLen = digits.size();
            
            if(sLen)  
            {
                res.push_back(string(sLen, '0'));
                for(i=0;i<sLen;++i)
                {
                    resSize = res.size();
                    res.resize(resSize * map[digits[i]-'0'].size()); // resize to extend to the next level
                    for(auto j=1; j<map[digits[i]-'0'].size();++j) // here j starts from 1 since we can use the original ones in the vector to add map[digits[i]][0]
                    {
                        std::copy(res.begin(),res.begin()+resSize, res.begin()+resSize*j); // copy the orignal vectors for each possible charactor corresponding to digits[i]
                        for(auto k=0; k<resSize;++k) res[resSize*j+k][i] = map[digits[i]-'0'][j]; // update the charactor
                    }
                    for(auto k=0; k<resSize;++k) res[k][i] = map[digits[i]-'0'][0]; 
                }
            }
            
            return res;
        
        }
    };

Log in to reply
 

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