题目描述
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
Example1:
Input: "aab" Output: [ ["aa","b"], ["a","a","b"] ]
解题思路
- 建立好这样一个二维数组dp，其中 dp[i][j] 表示 [i, j] 范围内的子串是否为回文串
- 回溯
- 参考这里
class Solution {
public:
vector<vector<bool>> dp;
vector<vector<string>> res;
vector<vector<string>> partition(string s) {
int n = s.size();
dp.resize(n, vector<bool>(n, false));
for(int i = 0; i < n; i++){
for(int j = 0; j <= i; j++){
if((s[j] == s[i] && (i - j <= 2 || dp[j + 1][i - 1]))){
dp[j][i] = true;
}
}
}
vector<string> path;
back_tracking(s, 0, path);
return res;
}
void back_tracking(string s, int index, vector<string>& path){
if(index == s.size()){
res.push_back(path);
return;
}
for(int i = index; i < s.size(); i++){
if(dp[index][i]){
path.push_back(s.substr(index, i - index + 1));
back_tracking(s, i + 1, path);
path.pop_back();
}
}
}
};
