131. 分割回文串(leetcode)
题目描述
给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是回文串 。返回 s 所有可能的分割方案。
示例1
输入:s = “aab”
输出:[[“a”,“a”,“b”],[“aa”,“b”]]
示例2
输入:s = “a”
输出:[[“a”]]
提示信息
1 <= s.length <= 16
s 仅由小写英文字母组成
题解1(C++版本)
class Solution {
public:
vector<vector<string>> res;
vector<string> t;
bool judge(string& s, int L, int R){
for(int i = L, j = R; i < j; i++, j--){
if(s[i] != s[j]) return false;
}
return true;
}
void dfs(string& s, int k){
if(k == s.size()){ // 找到一个分割回文串的方案
res.push_back(t);
return ;
}
if(k > s.size()) return ;
for(int i = k; i < s.size(); i++){
if(judge(s, k, i)){ // 判断字符串s[k, i]这段区间是否是回文子串
t.push_back(s.substr(k, i - k + 1)); // 截取区间[k,i]这段子串
dfs(s, i + 1);
t.pop_back(); // 回溯
}
}
}
vector<vector<string>> partition(string s) {
dfs(s, 0);
return res;
}
};