题解 | #所有的回文子串I# 回溯

知识点

回溯 DFS

思路

首先范围很小，而且需要枚举全部方案，可以考虑暴搜的方法。从前往后枚举原串，考虑每个字符是加入上一个串还是成为下一个串，这样对原串进行回溯。由于每个字符有两种选择，一共是种选择。

如果选择当前字符要成为新字符，那必须上一个串满足回文串的条件。判断回文串的时间复杂度为

总体复杂度为

要求字典序递增，可以先遍历成为新串的方向。

AC code（C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串vector<vector<>>
     */
    vector<vector<string> > partition(string s) {
        vector<vector<string>> res;
        vector<string> path;
        string ss;
        function<void(vector<string>&, string&, int)> dfs = [&](vector<string>& path, string& cur, int u) {
            if (u == s.size()) {
                if (cur.empty()) res.push_back(path);
                return;
            }
            cur.push_back(s[u]);
            if (check(cur)) {
                path.push_back(cur);
                string t;
                dfs(path, t, u + 1);
                path.pop_back();
            }
            dfs(path, cur, u + 1);
            cur.pop_back();
        };
        dfs(path, ss, 0);
        return res;
    }
    bool check(string& s) {
        if (s.empty()) return false;
        for (int i = 0, j = (int)s.size() - 1; i < j; i ++, j --) {
            if (s[i] != s[j]) return false;
        }
        return true;
    }
};