LeetCode 131 分割回文串

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

    bool is(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 dfs(int start, string s) {
        if (start == s.size()) { //start走到最后一个位置
            res.push_back(path);
            return;
        }

        for (int i = start; i < s.size(); i ++) {
            if (is(s, start, i)) {
                string temp = s.substr(start, i - start + 1);
                path.push_back(temp); //从start开始到i长度为i - start + 1
            }
            else continue;

            dfs(i + 1, s);
            path.pop_back();
        }
    }
    vector<vector<string>> partition(string s) {
        if (s.size() == 1) {
            path.push_back(s);
            res.push_back(path);
            return res;
        }

        dfs(0,s);

        return res;
    }
};