leetcode 热题100（131. 分割回文串）c++

链接：131. 分割回文串 - 力扣（LeetCode）

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 

回文串

 。返回 s 所有可能的分割方案。

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

提示：

• 1 <= s.length <= 16
• s 仅由小写英文字母组成

思路

        首先一看到数据范围这么小，很明显就是要我们dfs搜索的，然后这题还是求最大回文串的，那么我们知道肯定得先判断一下当前数组是否是回文串，不是的话就不添加，否则就添加进去。

判断回文串我们知道可以用记忆化搜索，如果我们之前搜过了当前子串，我们可以给他赋值1和-1，

1表示当前子串是回文串，-1表示不是，这样子我们就可以很快的判断是否是回文串了，就直接套回溯dfs模板直接写即可

代码

class Solution {
public:vector<vector<string>> res;vector<string> ans;int n;int f[18][18];void dfs(int p,string s){cout<<p<<endl;if(p>=s.size()){    //已经到达右端点无需遍历了，直接添加res.push_back(ans);return;}for(int i=1;i<=n;i++){//表示枚举的长度if(p+i<=n && isflag(p,p+i-1,s)==1){ //当前子串是回文串， ans.push_back(s.substr(p,i));dfs(p+i,s);ans.pop_back();}}}int isflag(int i,int j,string s){if(f[i][j]) return f[i][j];if(i>=j) return f[i][j]=1;return f[i][j]=(s[i]==s[j])?isflag(i+1,j-1,s):-1;}vector<vector<string>> partition(string s) {n = s.size();dfs(0,s);return res;}};