Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
Example:
Input: "aab" Output: [ ["aa","b"], ["a","a","b"] ]
本题要求把字符串s分割成若干个子串，使得每个子串都是回文串。如果有多种分割方法，输出所有的分割方案。 很有意思的一道题。我是这样做的：首先用DP求出任意一个子串s[i,…,j]是否为回文串，这就相当于知道了s中哪几个位置可以切割；然后就在s中DFS每个割点，求出所有的分割方案。
DP求s[i,…,j]是否为回文串的过程是这样的，如果s[i]==s[j]，且dp[i+1][j-1]也是回文串，则dp[i][j]也是回文串。所以我们需要先求到长度比较短的s[i+1,j-1]是否为回文串，然后再求长度更长的是否为回文串。所以在helper函数的外层循环是子串的长度。
求到了任意一个子串是否为回文串之后，DFS每个割点就好了，这个和枚举排列情况很类似，就不再赘述了。完整代码如下：
class Solution {
private:
void helper(const string& s, vector<vector<int> >& dp)
{
int n = s.size();
for (int i = 0; i < n; ++i)
dp[i][i] = 1; // 单个字符自身就是回文串
for (int len = 2; len <= n; ++len) {
for (int i = 0; i + len – 1 < n; ++i) {
if (s[i] == s[i + len – 1] && ((i + 1 <= i + len – 2 && dp[i + 1][i + len – 2] == 1) || i + 1 > i + len – 2)) {
dp[i][i + len – 1] = 1;
}
}
}
}
void dfs(const string& s, vector<vector<int> >& dp, vector<vector<string> >& ans, vector<string>& cand, int idx)
{
if (idx == s.size()) {
ans.push_back(cand);
return;
}
for (int i = idx; i < s.size(); ++i) {
if (dp[idx][i] == 1) {
cand.push_back(s.substr(idx, i – idx + 1));
dfs(s, dp, ans, cand, i + 1);
cand.pop_back();
}
}
}
public:
vector<vector<string> > partition(string s)
{
int n = s.size();
vector<vector<int> > dp(n, vector<int>(n, 0));
helper(s, dp);
vector<vector<string> > ans;
vector<string> cand;
dfs(s, dp, ans, cand, 0);
return ans;
}
};本代码提交AC，用时6MS。
二刷。不用DP提前判断，而是每次都暴力判断是否为回文：
class Solution {
public:
bool IsPal(const string &s, int l, int r) {
if (l > r)return false;
if (l == r)return true;
while (l < r) {
if (s[l] != s[r])break;
++l;
--r;
}
return l >= r;
}
void DFS(vector<vector<string>> &ans, vector<string> &cur, string &s, int idx) {
int n = s.size();
if (idx >= n) {
ans.push_back(cur);
return;
}
for (int i = idx; i < n; ++i) {
if (IsPal(s, idx, i)) {
cur.push_back(s.substr(idx, i - idx + 1));
DFS(ans, cur, s, i + 1);
cur.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
vector<vector<string>> ans;
vector<string> cur;
DFS(ans, cur, s, 0);
return ans;
}
};本代码提交AC，用时12MS，比第一种方法慢，还是第一种方法提前求DP更高效。