Dp solution with constraints


  • 0
    S
    class Solution {
    public:
        void dfs(vector<string> &res, string sentence, string s, int start, unordered_set<string> dict, bool p[]){
            if(start==s.size()){
                res.push_back(sentence.substr(1));
                return;
            }
            for(int i=start; i<s.size(); i++){
                if(dict.count(s.substr(start, i-start+1))>0&&p[i+1]){
                    dfs(res, sentence+" "+s.substr(start, i-start+1), s, i+1, dict, p);
                }
            }
        }
        vector<string> wordBreak(string s, unordered_set<string> &dict) {
            int n=s.size();
            bool p[n+1]; //p[i] is true if s[i..n-1] can be divided to words in dict
            for(int i=0; i<n; i++) p[i]=false;
            p[n]=true;
            for(int i=n-1; i>=0; i--){
                for(int j=i; j<n; j++){
                    if(dict.count(s.substr(i, j-i+1))>0&&p[j+1]) p[i]=true;
                }
            }
            vector<string> res;
            string sentence="";
            dfs(res, sentence, s, 0, dict, p);
            return res;
        }
    };

Log in to reply
 

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