题目描述

给定一个字符串 $s$，将 $s$ 划分成若干部分，使得每一部分都是回文串。

请返回所有合法的划分方案。

样例

输入："aab"
输出：
[
  ["aa","b"],
  ["a","a","b"]
]

算法

(暴搜+剪枝) $O(2^nn)$

暴力枚举所有方案。

对字符串从前往后搜索，搜索时维护如下几个状态：

1. 已经划分好的区间列表；
2. 当前正在枚举的区间；
3. 枚举到的字符串 $s$ 的下标；
4. 字符串 $s$；

在搜索时：分情况处理：

• 如果已经遍历完字符串 $s$，则递归终止。终止前判断方案是否合法：即判断当前区间是否是回文串；
• 否则，字符串 $s$ 还没遍历完，则
  • 如果当前区间不是回文串，则只能继续在该区间添加字符；
  • 如果当前区间是回文串，则既可以在该区间添加字符，也可以将该区间保存，并开启一个新的区间；

时间复杂度分析：首先考虑最多有多少个合法方案，我们可以考虑在相邻字符之间放板子，每种放板子的方法都对应一种划分方案，而每个字符间隔有放和不放两种选择，所以总共有 $2^{n-1}$ 个方案。另外对于每个方案，需要 $O(n)$ 的时间记录方案。所以总时间复杂度是 $O(2^nn)$。

C++ 代码

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

    vector<vector<string>> partition(string s) {
        dfs("", 0, s);
        return ans;
    }

    bool check(string &now)
    {
        if (now.empty()) return false;
        for (int i = 0, j = now.size() - 1; i < j; i ++, j -- )
            if (now[i] != now[j])
                return false;
        return true;
    }

    void dfs(string now, int u, string &s)
    {
        if (u == s.size())
        {
            if (check(now))
            {
                path.push_back(now);
                ans.push_back(path);
                path.pop_back();
            }
            return;
        }

        if (check(now))
        {
            path.push_back(now);
            dfs("", u, s);
            path.pop_back();
        }

        dfs(now + s[u], u + 1, s);
    }
};