目录

• • 题目描述
  • 题目大意
  • 回溯法+动态规划
  • 复杂度分析

---

题目来源：https://leetcode-cn.com/problems/next-greater-element-ii/

题目描述

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

输入: “aab”
输出:
[
[“aa”,“b”],
[“a”,“a”,“b”]
]

题目大意

• 看到题目的第一眼可能可以想到跟dp会有点关系，动态规划是处理子问题常见的方法之一，把问题分为一个个若干的子问题再进行求解
• 可以思考一下，假设当某一子串已经是回文串，此时若将子串进行扩张，扩张后的子串是回文串的充要条件是子串是回文串且子串的两个端点字符相等（此处无需用双指针重新比较回文串，是因为原子串已满足）
• 状态方程如下，当i≥j的时候为True，此处其实可以不看i>j的情况，从最小的子问题，单个字符（s[0]或s[s.length()-1]都可以）组成的字符串为回文串开始处理，再逐渐扩展到F(0,s.length())
  F ( i , j ) = { T r u e i ≥ j F ( i + 1 , j − 1 ) & & ( s [ i ] = = s [ j ] ) i < j F(i,j)= \left \{ \begin{array} {c}True{\quad}i≥j \\F(i + 1, j - 1)\&\&(s[i]==s[j]){\quad}i<j \end{array} \right. F(i,j)={Truei≥jF(i+1,j−1)&&(s[i]==s[j])i<j​

回溯法+动态规划

• 有了上述的状态方程，则可以用动态规划对字符串进行一个预处理，然后再通过dfs遍历的方式对字符串进行遍历（表面遍历F(i,j)，实质是对字符串划分所有子串再判断当前字符串是否满足回文串的条件（此处有了动态规划的预处理，判断条件时间复杂度O(1)））
• 对字符串划分所有子串的递归法(dfs)可见这篇文章，原理上是一样的https://blog.csdn.net/lr_shadow/article/details/113934454

class Solution {
public:
    vector<vector<string>> ans;
    vector<vector<int>> f;
    vector<string> ret;
    int n;

    void dfs(const string& s, int i){
        if(i == n){
            ans.push_back(ret);
            return;
        }
        for(int j = i ; j < n; ++j){
            if(f[i][j]){
                ret.push_back(s.substr(i, j - i + 1));
                dfs(s, j + 1);
                ret.pop_back();
            }
        }
    }

    vector<vector<string>> partition(string s) {
        n = s.length();
        f.assign(n, vector<int>(n, true));

        for(int i = n - 1 ; i >= 0 ; --i){
            for(int j = i + 1 ; j < n ; ++j){
                f[i][j] = f[i + 1][j - 1] && (s[i] == s[j]);
            }
        }
        dfs(s, 0);
        return ans;
    }
};

复杂度分析

• 时间复杂度：O(n*2^n)。n为字符串的长度，最坏情况下，s包含n个完全相同的字符，总共划分有2^n-1情况，每个情况需要O(n)的时间构建
• 空间复杂度：O(n*2^n)。最坏情况下划分为2^n-1个字符串，每个都需要O(n)空间