131 Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return

[
  ["aa","b"],
  ["a","a","b"]
]

Solution

class Solution {
public:
    bool isPalindrome(string s) {
        string r_s = s;
        reverse(r_s.begin(), r_s.end());
        return ( r_s == s);
    }
    vector<vector<string>> partition(string s) {
        vector<vector<vector<string>>> res;
        int n = s.size();
        if ( n == 0 ) {vector<vector<string>> tmp1; return tmp1;}
        vector<vector<string>> tmp1(1, vector<string>(1, s.substr(0, 1)));
        res.push_back(tmp1);
        for ( int i = 1; i <= n-1; i++ ) {
            vector<vector<string>> tmp2;
            for ( int j = i-1; j >= 0; j-- ) {
                if ( not isPalindrome(s.substr(j+1, i-j) ) ) continue;
                for ( int k = 0; k <= res[j].size()-1; k++ ) {
                    vector<string> tmp3 = res[j][k];
                    tmp3.push_back(s.substr(j+1, i-j));
                    tmp2.push_back(tmp3);
                }
            }
            if ( isPalindrome(s.substr(0, i+1))) {
                vector<string> tmp3(1, s.substr(0, i+1));
                tmp2.push_back(tmp3);
            }
            res.push_back(tmp2);
        }
        return res[n-1];
    }
};

Notes

vector<vector<vector<string>>> res;

Use the above variable to record the result.

• res[i] represents the palidrome partition for s[0:i].
• res[i] = {partitions in res[j]} + s[j+1:i+1]
  for any j that 0 <= j <= i-1 and s[j+1: i+1] is palindrom string.

Optimized solution
Use a 2D matrix (isPal) to record wether s[i:j+1] is palindrome or not.

class Solution {
public:
    bool isPalindrome(string s) {
        string r_s = s;
        reverse(r_s.begin(), r_s.end());
        return ( r_s == s);
    }
    vector<vector<string>> partition(string s) {
        vector<vector<vector<string>>> res;
        int n = s.size();
        if ( n == 0 ) {vector<vector<string>> tmp1; return tmp1;}
        vector<vector<string>> tmp1(1, vector<string>(1, s.substr(0, 1)));
        res.push_back(tmp1);
        vector<vector<bool>> isPal(n, vector<bool>(n, false));
        for ( int i = 0; i <= n-1; i++ ) {
            for ( int j = i; j <= n-1; j++ ) isPal[i][j] = isPalindrome(s.substr(i, j-i+1));
        }
        for ( int i = 1; i <= n-1; i++ ) {
            vector<vector<string>> tmp2;
            for ( int j = 0; j <= i-1; j++ ) {
                if ( not isPal[j+1][i] ) continue;
                for ( int k = 0; k <= res[j].size()-1; k++ ) {
                    vector<string> tmp3 = res[j][k];
                    tmp3.push_back(s.substr(j+1, i-j));
                    tmp2.push_back(tmp3);
                }
            }
            if ( isPal[0][i]) {
                vector<string> tmp3(1, s.substr(0, i+1));
                tmp2.push_back(tmp3);
            }
            res.push_back(tmp2);
        }
        return res[n-1];
    }
};

Further optimization
A faster solution to generate isPal matrix

vector<vector<bool>> isPal(n, vector<bool>(n, false));
        for ( int i = n-1; i >= 0; i-- ) {
            for ( int j = i; j <= n-1; j++ ){
                if ( ( j-i <= 1 or isPal[i+1][j-1] ) and s[i] == s[j] ) {
                    isPal[i][j] = true;
                }
            }
        }

• Be careful that $$s[i+1][j-1]$$ has to be assigned before $$s[i][j]$$. So i is in descending order, while j is in ascedning order!!