Typical DP solution


  • 0
    S
    class Solution {
    public:
        void helper(string s,vector<string>& tmp,vector<vector<string>>& res,vector<vector<bool>>& dp,int start) {
            if(start>=s.length()&&!tmp.empty()) {
                res.push_back(tmp);
            }
            for(int i=start;i<s.length();i++) {
                if(dp[start][i]==true) {
                    tmp.push_back(s.substr(start,i-start+1));
                    helper(s,tmp,res,dp,i+1);
                    tmp.pop_back();
                }
            }
        }
        vector<vector<string>> partition(string s) {
            int l=s.length();
            //vector<vector<bool>> dp;
           vector<vector<bool>> dp(l+1,vector<bool>(l+1,false));
            for(int i=l-1;i>=0;i--) {
                dp[i][i]=true;
                for(int j=i+1;j<l;j++) {
                    if((s[i]==s[j])&&((dp[i+1][j-1]==true)||(j-i)==1)){
                        dp[i][j]=true;
                    }
                }
            }
            for(int i=0;i<l;i++) {
                for(int j=i;j<l;j++) {
                    cout<<dp[i][j]<<",";
                }
                cout<<endl;
            }
            vector<string> tmp;
            vector<vector<string>> res;
            helper(s,tmp,res,dp,0);
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.