学步园

题目：

  [
    ["aa","b"],
    ["a","a","b"]
  ]

解题：

先用dp记录回文串，dp[i][j]表示s串从i到j为回文，状态转移：如果s[i] == s[j]，并且i == j || j == i + 1 || dp[i + 1][j - 1] == 1则标记dp[i][j]为1，表示是回文

然后暴力dfs。

代码如下：

class Solution {
public:
    vector<vector<string> > partition(string s) {
        makeDP(s);
        ans.clear(), single.clear();
        dfs(0, s);
        return ans;
    }
private:
    static const int SIZE = 1000;
    bool dp[SIZE][SIZE];
    vector<vector<string> > ans;
    vector<string> single;

    void makeDP(string s) {
        memset(dp, 0, sizeof(dp));
        for(int i = s.size() - 1; i >= 0; i --)
            for(int j = i; j < s.size(); j ++) 
                if(s[i] == s[j] && (i == j || j == i + 1 || dp[i + 1][j - 1]))
                    dp[i][j] = 1;
    }

    void dfs(int x, string s) {
        if(x == s.size()) {
            ans.push_back(single);
            return ;
        }
        for(int i = x; i < s.size(); i ++) {
            if(dp[x][i]) {
                string tmp;
                tmp.assign(s, x, i - x + 1);
                single.push_back(tmp);
                dfs(i + 1, s);
                single.pop_back();
            }
        }
    }
};