LeetCode Palindrome Partitioning

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

DP求s[i,...,j]是否为回文串的过程是这样的，如果s[i]==s[j]，且dp[i+1][j-1]也是回文串，则dp[i][j]也是回文串。所以我们需要先求到长度比较短的s[i+1,j-1]是否为回文串，然后再求长度更长的是否为回文串。所以在helper函数的外层循环是子串的长度。

```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;
}
};
```