Simple C++ backtrack easy to understand


  • 0
        vector<vector<string>> partition(string s) {
            vector<vector<string>>res;
            backtrack(res,s,0,vector<string>());
            return res;
        }
        
        void backtrack(vector<vector<string>>& res, string s, int pos, vector<string> comb){
            if(pos >= s.size()){
                res.push_back(comb);
                return;
            }
            // Palindrome length == 1
            comb.push_back(s.substr(pos,1));
            backtrack(res, s, pos + 1, comb);
            comb.pop_back();
            // Palindrome length > 1
            for(int step = 2; pos + step <= s.size(); step++){
                if(isPalindrome(s.substr(pos, step))){
                    comb.push_back(s.substr(pos, step));
                    backtrack(res, s, pos + step, comb);
                    comb.pop_back();
                }
            }
        }
        
        bool isPalindrome(string s){
            int i(0), j(s.size()-1);
            while(i < j) 
                if(s[i++] != s[j--]) return false;
            return true;
        }
    

    There are many problems can be solved in the similar way. You can check this post if interested - A template to those combination problems.


Log in to reply
 

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