回文字符串的切割

引用华科平凡大佬的原话，很精辟：

如要输出所有的解，往往深度优先搜索；
如要求出解的个数或最优解，往往动态规划

本题要求输出字符串的所有回文字串组合，因此用深度优先搜索（代码思路同样借鉴了大佬，判断回文的部分简直妙极了）：

//
// Created by jt on 2020/8/23.
//
#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    /**
     *
     * @param s string字符串
     * @return string字符串vector<vector<>>
     */
    vector<vector<string> > partition(string s) {
        // write code here
        vector<vector<string>> res;
        vector<string> vec;
        dfs(res, vec, s);
        return res;
    }

    void dfs(vector<vector<string>> &res, vector<string> &vec, string s) {
        if (s.size() < 1) { res.push_back(vec); return; }
        for (int i = 1; i <= s.size(); ++i) {   // ⚠️注意：i的含义是数组大小，因此这里是小于等于
            string sub = s.substr(0, i);
            if (isPalindrome(sub)) {
                vec.push_back(sub);
                dfs(res, vec, s.substr(i));
                vec.pop_back();
            }
        }
    }

    bool isPalindrome(string s) {
        return s == string(s.rbegin(), s.rend());
    }
};