官方制作网站,长沙网站seo报价,聊城网站设计咨询,深圳网站建设 猴王网络链接#xff1a;131. 分割回文串 - 力扣#xff08;LeetCode#xff09; 给你一个字符串 s#xff0c;请你将 s 分割成一些子串#xff0c;使每个子串都是
回文串 。返回 s 所有可能的分割方案。 示例 1#xff1a;
输入#xff1a;s aab
输出#xff…链接131. 分割回文串 - 力扣LeetCode 给你一个字符串 s请你将 s 分割成一些子串使每个子串都是
回文串 。返回 s 所有可能的分割方案。 示例 1
输入s aab
输出[[a,a,b],[aa,b]]示例 2
输入s a
输出[[a]]提示
1 s.length 16s 仅由小写英文字母组成 思路 首先一看到数据范围这么小很明显就是要我们dfs搜索的然后这题还是求最大回文串的那么我们知道肯定得先判断一下当前数组是否是回文串不是的话就不添加否则就添加进去。
判断回文串我们知道可以用记忆化搜索如果我们之前搜过了当前子串我们可以给他赋值1和-1
1表示当前子串是回文串-1表示不是这样子我们就可以很快的判断是否是回文串了就直接套回溯dfs模板直接写即可 代码
class Solution {
public:vectorvectorstring res;vectorstring ans;int n;int f[18][18];void dfs(int p,string s){coutpendl;if(ps.size()){ //已经到达右端点无需遍历了直接添加res.push_back(ans);return;}for(int i1;in;i){//表示枚举的长度if(pin isflag(p,pi-1,s)1){ //当前子串是回文串 ans.push_back(s.substr(p,i));dfs(pi,s);ans.pop_back();}}}int isflag(int i,int j,string s){if(f[i][j]) return f[i][j];if(ij) return f[i][j]1;return f[i][j](s[i]s[j])?isflag(i1,j-1,s):-1;}vectorvectorstring partition(string s) {n s.size();dfs(0,s);return res;}};
