LeetCode131：分割回文串

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

代码

class Solution {
public:
    vector<vector<string>> res;
    vector<string> path;

    bool isPalindrome(const string &s, int start, int end) {
        while (start < end) {
            if (s[start] != s[end]) {
                return false;
            }
            ++start;
            --end;
        }
        return true;
    }
    
    void backTracking(const string &s, int startIndex) {
        //startIndex作为切割线
        if (startIndex >= s.size()) {
            res.push_back(path);
            return;
        }

        for (int i = startIndex; i < s.size(); i++) {
            //是回文串
            if (isPalindrome(s, startIndex, i)) {
                /*
                    截取字符串的一段
                    方法1
                    string tmp(s.begin() + startIndex, s.begin() + i+1);
                    方法2
                    s.substr (pos, n) ，pos表示要截取的字符串的开始的位置，n 代表要截取的字符串的长度。
                    s.substr(pos) , 表示从pos位置开始的 到字符串最后一位截取的字符串

                    s.substr(startIndex,i-startindex+1);
                */
                string tmp = s.substr(startIndex, i - startIndex + 1);
                path.push_back(tmp);
            }
            else
                continue;

            backTracking(s, i + 1);
            path.pop_back();
        }
    }

    vector<vector<string>> partition(string s) {
        if (s.size() == 0) return res;
        backTracking(s, 0);
        return res;
    }
};