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

这题挺难的，搞了两个小时才一知半解吧qaq

思路：首先要明白什么作为终止条件，其次就是for循环内什么时候插入path，剩下的就是套模板了，其次补充一下回文数的判断即可

class Solution {
private:vector<vector<string>> result;vector<string> path;void backtracking(const string& s,int startIndex){if(startIndex>=s.size()){//为什么仅需判断大小即可，不会出现找不到的情况吗？result.push_back(path);return;}for(int i=startIndex;i<s.size();i++){if(ishui(s,startIndex,i)){string str=s.substr(startIndex,i-startIndex+1);//一开始分割为一个个的时候，i和index不是一直一样吗，什么时候i会大于startIndex呢path.push_back(str);}else continue;//如果不加会怎么样？backtracking(s,i+1);path.pop_back();}}bool ishui(const string& s,int startIndex,int end){for(int i=startIndex,j=end;i<j;i++,j--){if(s[i]!=s[j]) return false;}return true;}
public:vector<vector<string>> partition(string s) {backtracking(s,0);return result;}
};

ps：代码注释是我第一次写的时候的疑问

总结：1.为什么仅需判断大小？因为只要非空字符串必有一组可以成立的分割组合，而index代表开始分割的位置，当分割到最后一个或大于最后一个，即全部分割完了

2.什么时候i开始变得？当横向遍历，尝试分割更长的字符串时（这里是横向和纵向没了解清楚），横向的时候startIndex是不变的，变得是末端i的位置。

横向：初次分割的位置，剩下的没分割的就交给纵向分割。

纵向：选择了第一次分割的若干情况的一种，然后继续分割剩余的情况

3.若漏了continue？会遍历无效组合，比如说横向分割的时候就不是回文串，纵向时又找到若干组合，但起始就是错的就会出现很多无效组合，所以一定要跳过无效的横向组合。