代码随想录 回溯

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？会遍历无效组合，比如说横向分割的时候就不是回文串，纵向时又找到若干组合，但起始就是错的就会出现很多无效组合，所以一定要跳过无效的横向组合。