LeetCode 131. 分割回文串

LeetCode 131. 分割回文串

思路：

先维护一个f数组，把所有的回文字符都标记出来，这样是因为回文字符是可以递归的找出来的，
第一种情况：
长度是1。
第二种情况：
两端字符相等，且中间的是回文字符，还要考虑一种特殊的情况就是只有两个字符，这样情况下，简单的判断两端以及中间(空)是不行的，这种情况是 i + 1 > j - 1。

代码：

class Solution {
public:
    vector<vector<bool>> f;
    vector<vector<string>> res;
    vector<string> path;

    vector<vector<string>> partition(string s) {
        int n=s.size();
        f = vector<vector<bool>> (n,vector<bool> (n));

        for (int j = 0; j < n; j ++ )
            // 前面的位置 是小于 后面的位置的
            for (int i = 0; i <= j; i ++ )
                if (i == j) f[i][j] = true;
                else if (s[i] == s[j]) {
                    if (i + 1 > j - 1 || f[i + 1][j - 1]) f[i][j] = true;
                }

        dfs(s,0);
        return res;
    }

    void dfs(string &s,int u){
        if(u == s.size()){
            res.push_back(path);
        }
        else{
            for(int i = u;i<s.size();i++){
                if(f[u][i]){
                    path.push_back(s.substr(u,i - u + 1));
                    dfs(s,i+1);
                    path.pop_back();
                }
            }
        }
    }
};