C++ 12ms dp solution


  • 4

    The flag can be used to save repetitive examinations of of bad substrs.

    class Solution {
    public:
    void helper(vector<bool>& flag, string s, int n, string pre, vector<string> &res, unordered_set<string>& wordDict){
        if (n>=s.size()) {res.push_back(pre);return;}
        for (int i=n;i<s.size();i++){
            if (flag[i+1] && wordDict.find(s.substr(n,i-n+1))!=wordDict.end()){
                helper(flag,s,i+1,pre+s.substr(n,i-n+1)+" ",res,wordDict);
            }
        }
    }
    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
        vector<string> res;
        if (s.empty()) {res.push_back("");return res;}
        int k=s.size();
        vector<bool> flag(k+1,0);
        flag[k] = 1;
        for (int i=k-1;i>=0;i--){
            int j=i;
            while(j<=k-1){
                if (flag[j+1] && wordDict.find(s.substr(i,j-i+1))!=wordDict.end()){
                    flag[i] = 1;break;
                }
                j++;
            }
        }
        if (flag[0]==0) return res;   // no possible solution if flag[0]==false
        helper(flag,s,0, "",res,wordDict);
        for (auto &s:res){
            s.pop_back();
        }
        return res;
    }
    };

  • 0
    P

    can you explain your solution?


Log in to reply
 

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