Palindrome Partitioning

Description

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example

Given s ="aab", return:

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

Related problems

Palindrome Partitioning II (Actually a DP issue)

Implementation

Link: http://lintcode.com/en/problem/palindrome-partitioning/

class Solution {
public:
    /**
     * @param s: A string
     * @return: A list of lists of string
     */
    vector<vector<string>> partition(string s) {
        // write your code here
        vector<vector<string>> answer;
        vector<string> path;

        if(s.size() == 0) return answer;

        helper(s, answer, path, 0);
        return answer;
    }

    void helper(string & s, vector<vector<string>> & answer, vector<string> & path, int start){
        if(start == s.size()){
            answer.push_back(path);
            return;
        }

        for(int i = start; i < s.size(); i++){
            if(palindrome(s, start, i)){
                path.push_back(s.substr(start, i - start + 1));
                helper(s, answer, path, i + 1);
                path.pop_back();
            }
        }
    }

    bool palindrome(string & s, int start, int end){
        if(start > end) return false;

        while(start < end){
            if(s[start++] != s[end--]) return false;
        }
        return true;
    }
};