Problem
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
A palindrome string is a string that reads the same backward as forward.
Constraints:
- 1 <= s.length <= 16
- s contains only lowercase English letters.
Example1
Input: s = “aab”
Output: [[“a”,“a”,“b”],[“aa”,“b”]]
Example2
Input: s = “a”
Output: [[“a”]]
Solution
class Solution {
public:
vector<vector<bool>> f;
vector<vector<string>> ans;
vector<string> path;
vector<vector<string>> partition(string s) {
int n = s.size();
f = vector<vector<bool>>(n, vector<bool>(n));
for (int j = 0; j < n; j ++ )
for (int i = 0; i <= j; i ++ )
if (i == j) f[i][j] = true;
else if (s[i] == s[j]) {
cout<<i<<" "<<j<<endl;
if (i + 1 > j - 1 || f[i + 1][j - 1]) f[i][j] = true;
}
dfs(s, 0);
return ans;
}
void dfs(string& s, int u) {
if (u == s.size()) ans.push_back(path);
else {
for (int i = u; i < s.size(); i ++ )
if (f[u][i]) {
path.push_back(s.substr(u, i - u + 1));
dfs(s, i + 1);
path.pop_back();
}
}
}
};