Leecode 131. 分割回文串 DFS+回溯

原题链接：Leecode 131. 分割回文串

动态规划预处理+回溯

class Solution {
public:
    vector> res;
    vector> f;
    vector t;
    void dfs(string s,int i)
    {
        if(i==s.size())
        {
            res.push_back(t);
            return;
        }
        for(int j=i;j
            if(f[i][j])
            {
                string tmp=s.substr(i,j-i+1);
                t.push_back(tmp);
                dfs(s,j+1);
                t.pop_back();
            }
        }
    }
    vector> partition(string s) {
        int n=s.size();
        f=vector>(n,vector(n,true));
        for(int i=n-1;i>=0;i--)
        {
            for(int j=i+1;j
                f[i][j]=(s[i]==s[j]) && f[i+1][j-1];
            }
        }
        dfs(s,0);
        return res;
    }
};

函数判断是否回文串+回溯

class Solution {
public:
    vector> res;
    vector t;
    bool judge(string s)
    {
        int l=0,r=s.size()-1;
        while(l
            if(s[l]==s[r]) 
            { l++;r--; }
            else return false;
        }
        return true;
    }
    void dfs(string s,int i)
    {
        if(i==s.size())
        {
            res.push_back(t);
            return;
        }
        for(int j=i;j
            string tmp=s.substr(i,j-i+1);
            if(judge(tmp))
            {
                t.push_back(tmp);
                dfs(s,j+1);
                t.pop_back();
            }
        }
    }
    vector> partition(string s) {
        int n=s.size();
        dfs(s,0);
        return res;
    }
};