Accepted c++ solution - backtracking


  • 0
    M
    class Solution {
        public:
            vector<vector<string>> partition(string s) {
                vector<vector<string>> res;
                vector<string> p;
                findPartition(res, p, s, 0);
                return res;
            }
            
        private:
            void findPartition(vector<vector<string>>& res, vector<string>& p, string& s, int begin){
                if(begin >= s.size()){
                    res.push_back(p);
                    return;
            }
            
            string ss;
            for(int i = begin; i < s.size(); i++){
                ss += s[i];
                
                if(isPalindrome(ss) == false) continue;
                
                p.push_back(ss);
                findPartition(res, p, s, i+1);
                p.pop_back();
            }
        }
        
        bool isPalindrome(string& s){
            int front = 0; 
            int back = s.size()-1;
            
            while(front < back){
                if(s[front] != s[back]) return false;
                front++;
                back--;
            }
            return true;
        }
    };

Log in to reply
 

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