专业的聊城做网站费用/帮别人发广告赚钱平台

131. 分割回文串
经典回溯题。

理论上来讲，是要进行回文的判定的预处理的。
但是时间复杂度已经是指数级的，优化一下，意义不是很大。

class Solution {
public:vector<vector<string>> ans;// 记录分割结果vector<string> temp; vector<vector<string>> partition(string s) {dfs(0,s);return ans;}void dfs(int idx,const string& s){if(idx == s.size()){ans.push_back(temp);return;}for(int i = idx; i <s.size();i++){if(check(s,idx,i)){temp.push_back(s.substr(idx,i-idx+1));dfs(i+1,s);// 回溯temp.pop_back();}}}bool check(const string& s,int l,int r){int i = l, j = r;while(i<j){if(s[i] != s[j]){break;}i++;j--;}return i >= j;}
};