My C++ code (DP + recursion) 16ms


  • 0
    D
    class Solution {
    public:
    void    buildPartition(string &s, int pos, vector<vector<string> > &res, vector<vector<bool> > &isPal, vector<string> &curP)
    {
        int len, sSize = s.size();
    
        if(pos>= sSize) 
        {
            res.push_back(curP); // if it reaches the end successfully, which means curP has a valid solution, save it
            return;
        }
        
        for(len=1; len<= sSize-pos; len++)
        { // go through all possible cutting positions
            if(isPal[pos][len])
            { // if the left sub-string is valid, then recursively check the right sub-string
                curP.push_back(s.substr(pos, len));  // save the left sub-string
                buildPartition(s, pos+len, res, isPal, curP);
                curP.pop_back(); // when finished, pop up the left sub-string and move to the next possible left sub-string
            }
        }
    }    
        vector<vector<string>> partition(string s) {
            vector<vector<string> > res;
            int sSize = s.size();
            if(sSize > 0)
            {
                vector<vector<bool> > isPal(sSize, vector<bool>(sSize + 1, true)); // i:start pos, j: len of the substring
                int i, len;
                vector<string> curP;
                
                // build the sub-string palin "valid" table
                for(i =0; i<sSize-1; i++) isPal[i][2] = (s[i] == s[i+1]); // for 2-char substring
                for(len=3; len<=sSize; len++)
                {
                    for(i =0; i< (sSize-len + 1); i++) isPal[i][len] = (s[i] == s[i+len-1]) && isPal[i+1][len-2];
                }
    // recursively generate all possible cutting solutions
                buildPartition(s, 0, res, isPal, curP);
                
            }
            return res;
        }
    };

Log in to reply
 

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