每日一题 131 回溯+动态规划
文章目录
131. 分割回文串
给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例:
输入: "aab"
输出:
[
["aa","b"],
["a","a","b"]
]
思路DFS
- 一开始遇到这个题目考虑用递归,但不知道如何获得所有的可能结果
- 回溯,注意回溯的过程中需要每次入path的时候,都要记得最后弹出
class Solution {
public:
vector<vector<string>> res;
vector<string> path;
vector<vector<string>> partition(string s) {
res.clear();
path.clear();
back(s, path, 0);
return res;
}
void back(string &s, vector<string> &path, int start) {
if (start >= s.size()) {
res.push_back(path);
return;
}
for (int i = start; i < s.size(); i++) {
if (isPa(s, start, i)) {
string str = s.substr(start, i-start+1);
path.push_back(str);
} else {
continue;
}
back(s, path, i+1);
path.pop_back();
}
}
//双指针判断[start,end]是否为回文串
bool isPa(string &s, int start, int end) {
while (start < end) {
if (s[start] == s[end]) {
start++;
end--;
} else {
return false;
}
}
return true;
}
};
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论