原题

LintCode 136. 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"]
]

解题

题意为给定一个字符串，将其分割为每个字串都是回文字符串。给出所有的分割方法。

使用递归的方式，每个字符串都可以将前n个字符组成一个回文子串，剩下的字符继续传入递归。

代码

class Solution {
public:
    /*
    * @param s: A string
    * @return: A list of lists of string
    */
    vector<vector<string>> partition(string &s) {
        // write your code here
        helper(s);
        return ans;
    }
private:
    vector<vector<string>> ans;
    vector<string> cur;
    void helper(string str) {
        if (str.length()) {
            for (int i = 0; i < str.length(); i++) {
                string sub = str.substr(0, i + 1);
                if (check(sub)) {
                    cur.push_back(sub);
                    helper(str.substr(i + 1));
                    cur.pop_back();
                }
            }
        } else {
            ans.push_back(cur);
        }
    }
    bool check(string &str) {
        for (int i = 0, j = str.length() - 1; i < j; i++, j--) {
            if (str[i] != str[j]) return false;
        }
        return true;
    }
};