sundeepblue
3/18/2014 - 5:14 PM

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

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"] ]

Palindrome Partitioning.cpp
content_copyfile_download
// this dfs way is easy to TIMEOUT!!!
vector<vector<string>> palindrome_partition(string s) {
    vector<vector<string>> res;
    if(s.empty()) return res;
    vector<string> par;
    dfs(res, par, s, 0);
    return res;
}

bool is_palindrome(string s) {
    if(s.empty() || s.size() == 1) return true;
    int i = 0, j = s.size()-1;
    while(i <= j) {
        if(s[i] != s[j]) return false;
        i++;
        j--;
    }
    return true;
}

void dfs(vector<vector<string>> &res, vector<string> par, string s, int begin) {
    if(begin == s.size()) {
        res.push_back(par);
        return;
    }
    for(int i=begin; i<s.size(); i++) {
        string sub = s.substr(begin, i-begin+1);
        if(is_palindrome(sub) == false) continue;
        par.push_back(sub);
        dfs(res, par, s, i+1); // p0, should be s not s.substr(i+1) !!!
        par.pop_back();
    }
}