131. 分割回文串
3 min
题目
解法：回溯
思路
使用回溯算法（DFS）枚举所有可能的分割方式，通过递归和剪枝找出所有满足条件的回文分割方案。
该方法的正确性基于穷举思想。从字符串起始位置开始，我们尝试所有可能的切割点，对每个子串判断是否为回文。如果是回文，则递归处理剩余部分；否则跳过。当递归到达字符串末尾时，说明找到了一种完整的分割方案。通过回溯（撤销选择），我们可以探索所有可能的分支，不会遗漏任何有效解。
- Step 1: 从字符串的起始位置开始递归
- Step 2: 枚举从当前位置开始的所有可能的子串结束位置
- Step 3: 判断当前子串是否为回文串
- Step 4: 如果是回文，将其加入当前路径，递归处理剩余字符串
- Step 5: 回溯，弹出当前子串，尝试其他分割方式
- Step 6: 当处理到字符串末尾时，将当前路径加入结果集
复杂度
- 时间复杂度:
- 空间复杂度:
代码
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> ans;
vector<string> path;
dfs(s, 0, path, ans);
return ans;
}
void dfs(const string& s, int start, vector<string>& path, vector<vector<string>>& ans) {
if (start == s.size()) {
ans.push_back(path);
return;
}
for (int i = start; i < s.size(); i++) {
if (isPalindrome(s, start, i)) {
path.push_back(s.substr(start, i - start + 1));
dfs(s, i + 1, path, ans);
path.pop_back(); // 回溯
}
}
}
bool isPalindrome(const string& s, int left, int right) {
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> ans;
vector<string> path;
dfs(s, 0, path, ans);
return ans;
}
void dfs(const string& s, int start, vector<string>& path, vector<vector<string>>& ans) {
if (start == s.size()) {
ans.push_back(path);
return;
}
for (int i = start; i < s.size(); i++) {
if (isPalindrome(s, start, i)) {
path.push_back(s.substr(start, i - start + 1));
dfs(s, i + 1, path, ans);
path.pop_back(); // 回溯
}
}
}
bool isPalindrome(const string& s, int left, int right) {
while (left < right) {
if (s[left++] != s[right--]) return false;
}
return true;
}
};