8-line Backtracking-Function C++ Solution


  • 21
    L

    Most concise backtracking function, no?

    class Solution {
    public:
        vector<string> letterCombinations(string digits) 
        {
            vector<string> res;
            if(digits.size()==0) return res;
            string local;
            vector<vector<char>> table(2,vector<char>());
            table.push_back(vector<char>{'a','b','c'}); // index 2
            table.push_back(vector<char>{'d','e','f'}); // 3
            table.push_back(vector<char>{'g','h','i'});
            table.push_back(vector<char>{'j','k','l'}); // 5
            table.push_back(vector<char>{'m','n','o'});
            table.push_back(vector<char>{'p','q','r','s'}); // 7
            table.push_back(vector<char>{'t','u','v'});
            table.push_back(vector<char>{'w','x','y','z'}); // 9
            
            backtracking(table,res,local,0,digits);
            return res;
        }
        
        void backtracking(const vector<vector<char>>& table, vector<string>& res, string& local, int index, const string& digits) {
            if(index==digits.size())
                res.push_back(local);
            else
                for(int i=0;i<table[digits[index]-'0'].size();i++) {
                    local.push_back(table[digits[index]-'0'][i]);
                    backtracking(table, res, local, index+1, digits);
                    local.pop_back();
                }
        }
    };

  • 1
    R

    u could get the index from partial result, so four arguments 4 the backtracking function will be enough. just some personal opinion. your solution is quite nice.the difference is slight.

    class Solution {
    public:
        vector<string> letterCombinations(string digits) {
        	vector<string> ret;
        	if(0>=digits.size()) return ret;
        
        	const string map[]={"0","1","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        	backTrackingFun(map,digits,"",ret);
        
        	return ret;
        }
        
        void backTrackingFun(const string m[], const string &digits, string r, vector<string> &ret){
        	int c=r.size();
        	if(digits.size()==c){
        		ret.push_back(r);
        		return;
        	}
        
        	auto str = m[digits.at(c)-48];
        	for(auto it=str.cbegin();it!=str.cend();++it){
        		r.push_back(*it);
        		backTrackingFun(m,digits,r,ret);
        		r.pop_back();
        	}
        }
    };

  • 0
    Q

    actually, by introducing a few data member, one param does suffice.


  • 1
    T

    A more concise recursive solution with only one function:

        string num2alpha[8] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        vector<string> letterCombinations(string digits) {
            vector<string> result;
            if(digits.empty()) return result;
            char curDigit = digits[0];
            string curStr = num2alpha[curDigit-'2'];
            vector<string> subResult = letterCombinations(digits.substr(1));
            if(subResult.empty()) subResult.emplace_back("");
            for(int i = 0; i < curStr.length(); ++i)
            {
                for(int j = 0; j < subResult.size(); ++j)
                {
                    string tmp = "";
                    tmp += curStr[i];
                    tmp = tmp + subResult[j];
                    result.emplace_back(tmp);
                }
            }
            return result;
    }

  • 0
    P

    Hi, why do you need to pop_back()?


  • 1
    S

    that's how back tracking works.


  • 0
    K

    That's because he passed in a reference of the current building string, another way to do this without the pop_back() is to pass that string by value and you don't need to pop_back().


  • 0
    S

    @pei-heng This is the method about backtracking. If without this pop_back, it's DFS. With pop_back, we can go to the previous node and continue search in another way.


  • 0
    L

    what is the time complexity of the this backtracking algorithm? is it O(4^n), n is the length of the input string.


  • 0
    H
    
    vector<string> letterCombinations(string digits) {
            vector<string> res;
            if(digits.size() == 0) return res;
            string local;
            vector<vector<char>> table{{'0'}, {'1'}, {'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'}};
            
            backtracking(table, res, local, 0, digits);
            return res;
        }
        
        void backtracking(vector<vector<char>>& table, vector<string>& res, string& local, int index, string& digits){
            int digit = digits[index] - '0';
    
            if(index == digits.size())
                res.push_back(local);
            else
                for(int i = 0; i < table[digit].size(); i++){
                    local.push_back(table[digit][i]);
                    backtracking(table, res, local, index+1, digits);
                    local.pop_back();
                }
        }

Log in to reply
 

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