C++ recursion solution


  • 0
    S

    The idea is: loop find the first palindrome sub string(the sizeof sub string is 1.2.3.4...), then recursion find the rest string palinkdrome.

    class Solution {
    public:
        bool ispalindrome(string s){
            for(int i=0; i<s.size()/2; i++){
                if(s[i] != s[s.size()-1-i]){
                    return false;   
                }
            }
            return true;
        }
    
        void process(vector<vector<string>> &vv, vector<string> &vs, string s){
            if(s.size() == 0){
                vv.push_back(vs);
            }
            for(int i=1; i<=s.size(); i++){
                string substr = s.substr(0, i);
                if(ispalindrome(substr)){
                    vs.push_back(substr);
                    process(vv, vs, s.substr(i, s.size()-i));
                    vs.pop_back();
                }
            }
        }
    
        vector<vector<string>> partition(string s) {
            vector<string> vs;
            vector<vector<string>> vv;
            if(s.size() == 0) return vv;
            
            process(vv, vs, s);
            
            return vv;
        }
    };
    

Log in to reply
 

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