回溯-分割回文串_回溯 回文 go

class Solution {
private:
    vector<vector<string>> res;
    vector<string> path;
    //利用双指针来对回文进行判断
    bool isPalindrome(const string& s, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            if (s[i] != s[j]) {
                return false;
            }
        }
        return true;
    }
 
    void backTracking(string s, int startIndex) {
        if (startIndex >= s.size()) {
            res.push_back(path);
            return;
        }
        //判断的是[i, startIndex]这个区间是否回文
        for (int i = startIndex; i < s.size(); i++) {
            if (isPalindrome(s, startIndex, i)) {
                string str = s.substr(startIndex, i - startIndex + 1);
                path.push_back(str);
                backTracking(s, i + 1);
                path.pop_back();
            }
        }
    }
 
public:
    vector<vector<string>> partition(string s) {
        backTracking(s, 0);
        return res;
    }
};

 回溯的一个重要题型--切割问题

算法思想：其实和组合问题非常类似，组合问题的取数其实对应切割问题的切割，切割问题就是在某个地方切割，也就是答案中的i，切割下来的就是startIndex到i这一段，然后递归，再回溯。