131. Palindrome Partitioning 回文子串分割
131. Palindrome Partitioning 回文子串分割
思路
既然是子串，就有 start 和 end 两个端点，遍历字符串，start 从 0 开始，推进 end 寻找回文串，找到之后，将 start 继续向前推进，重复上述过程，这个过程可以递归查找，但是递归操作中如何记录已经找到的子串组合使得从不同位置开始找的回文串的时候，前面相同的部分都保存起来呢？这就需要用到回溯法，递归找完返回之后我们需要将我们当前已经搜过的回文串弹出，然后才能继续当前的搜索
DFS + 回溯
vector<vector<string>> partition(string s) {
vector<vector<string>> res;
vector<string> path;
if (s.size()==0) return res;
dfs(s, 0, path, res);
return res;
}
// DFS深搜
void dfs(string &s, int idx, vector<string>& path, vector<vector<string>> &res) {
// 对整个字符串的一次搜索结束，记录这一次搜索的子串集合
if (idx==s.size()) {
res.push_back(path);
return;
}
for(int i=idx;i<s.size();++i) {
// 从当前位置开始搜索回文串
if (isPalindrome(s, idx, i)) {
// 当前搜到的串保存起来
path.push_back(s.substr(idx, i-idx+1));
// 递归推进搜索
dfs(s, i+1, path, res);
// 回溯当前搜到的串，为下一个子串的搜索做准备
path.pop_back();
}
}
}
// 判断回文
bool isPalindrome(string &s, int i, int j) {
int hi=j;
int lo=i;
while(lo<hi) {
if (s[lo++]!=s[hi--]) return false;
}
return true;
}#回溯法 #回文串 #字符串 #DFS