题目描述

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]

题意：讲一个字符串拆分成若干个子串，使每个子串都是一个回文串。返回所有可能的拆分情况。

算法1

题解：首先我们预处理好哪些子串是回文串，这个可以用动态规划在$O(n^2)$的时间内处理好，dp[i][j]代表s[i:j]是回文串。然后进行递归搜索，u代表当前处理到哪个位置，我们从当前位置开始，枚举所有可能的回文子串，进行递归搜索直至处理完整个字符串。最坏的情况是整个字符串都是同一个字符，这需要$O(2^n)$时间复杂度

class Solution {
public:
    vector<vector<int>> dp;
    vector<vector<string>> res;
    vector<vector<string>> partition(string s) {
        int n = s.length();
        dp = vector<vector<int>> (n,vector<int>(n,0));
        dp[0][0] = 1;
        for(int i = 1 ; i < n ; i ++) 
            dp[i][i] = 1,dp[i - 1][i] = (s[i - 1] == s[i]);
        for(int len = 2; len < n ; len ++)
        {
            for(int i = 0 ; i + len < n ; i ++)
            {
                int j = i +len;
                dp[i][j] = (s[i] == s[j]) && (dp[i + 1][j - 1] == 1);
            }
        }
        vector<string> path;
        dfs(s,0,n,path);
        return res;
    }
    void dfs(string &s,int u,int n,vector<string> &path)
    {
        if(u == n){res.push_back(path);return;}
        for(int i = u ; i < n ; i ++)
        {
            if(dp[u][i] == 1)
            {
                path.push_back(s.substr(u,i - u + 1));
                dfs(s,i + 1,n,path);
                path.pop_back();
            }
        }
    }
};