LeetCode 分割回文串

131.分割回文串

给你一个字符串s，请你将s分割成一些 ，使每个子串都是。返回 s 所有可能的分割方案。

示例 1：

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

示例 2：

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

提示：

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

解题思路

1、判断回文字符串：双指针+while循环

2、每一个字符后都设想有一个分割点，枚举每个分割点，满足条件就放入temp数组中，然后进行下一次分割

代码

class Solution {
public:vector<vector<string>> partition(string s) {vector<vector<string>> res;vector<string> temp;int index=0;dfs(s,index,res,temp);return res;      }void dfs(string s,int index,vector<vector<string>>& res,vector<string>& temp){if(index>=s.size()){res.push_back(temp);return;}for(int i=index;i<s.size();i++){if(isHW(s,index,i)){temp.push_back(s.substr(index,i-index+1));dfs(s,i+1,res,temp);temp.pop_back();}}}//利用双指针判断回文序列bool isHW(string s,int left,int right){while(left<right){if(s[left]==s[right]){left++;right--;}else{return false;}}return true;}};