分割回文串
给你一个字符串 s
,请你将 s
分割成一些子串,使每个子串都是 回文串 。返回 s
所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
输入:s = "aab"
输出:[["a","a","b"],["aa","b"]]
算法:
暴搜加减枝
首先判断是否为回文串(回文串:两个指针,一前一后,如果不同,返回false)
从0索引暴力搜索,如果子串满足回文串,进行搜索,记得进行回溯
class Solution {
public:
vector<vector<string>> ans;
vector<string> path;
void dfs(string s, int u)
{
if(u == s.size())
{
ans.push_back(path);
return;
}
for(int i = u;i < s.size();i++)
{
if(check(s,u,i))
{
path.push_back(s.substr(u,i-u+1));
dfs(s,i+1);
path.pop_back();
}
}
}
vector<vector<string>> partition(string s)
{
dfs(s,0);
return ans;
}
bool check(string s,int l,int r)
{
while(l <= r)
{
if(s[l] == s[r])
{
l++;
r--;
}
else
return false;
}
return true;
}
};