c++ backtracking solution


  • 0
    B
    class Solution {
    public:
        vector<vector<string>> result;
        
        void dfs(vector<string> cur, string s, int start){
            int n=s.length();
            
            if(start>=n){
                result.push_back(cur);
                return;
            }
            
            for(int i=start;i<n;i++){
                if(palindrome(s,start,i)){
                    cur.push_back(s.substr(start,i-start+1));
                    dfs(cur, s, i+1);
                    cur.pop_back();
                }
                
            }
            return ;
        }
    
        bool palindrome(string s, int start, int end){
            if(start<0 || end>s.length()-1) return false;
            
            while(start<end){
                if(s[start++]!=s[end--]) return false;
            }
            
            return true;
        }
        
        vector<vector<string>> partition(string s) {
            if(!s.size()) return result;
            vector<string> cur;
            
            dfs(cur, s, 0);
            return result;
        }
    };
    

Log in to reply
 

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