leetcode 140 Word Break II

leetcode 139 word break

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordset(wordDict.begin(),wordDict.end());
        vector<int> memo(s.size(),-1);
        return check(s,wordset,0,memo);
    }
    
    bool check(const string &s,unordered_set<string> &wordset,int start,vector<int> &memo)
    {
        if(start>=s.size()) return true;
        if(memo[start]!=-1) return memo[start];
        for(int i=start+1;i<=s.size();++i)
        {
            if(wordset.count(s.substr(start,i-start))&&check(s,wordset,i,memo))
            {
                return memo[start]=1;
            }
        }
        return memo[start]=0;
    }
};

leetcode 140

1. 用hashset存储wordDict，查找效率高；unordered_map<int,vector<string>>记忆数组，存储从位置i开始，所有可能的情况。

class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> words(wordDict.begin(),wordDict.end());
        unordered_map<int,vector<string>> memo;
        helper(s,0,words,memo);
        return memo[0];
    }
   vector<string> helper(string& s,int start,unordered_set<string>& words,unordered_map<int,vector<string>> &memo) {
        if(start>=s.size()) return {""};
        if(memo.find(start)!=memo.end()) return memo[start];
        for(int i=start+1;i<=s.size();++i) {
            string tmp=s.substr(start,i-start);
            if(words.find(tmp)!=words.end()) {
                auto vals=helper(s,i,words,memo);
                for(auto& val:vals) memo[start].push_back(tmp+(val.empty()?"":" ")+val);
            }
        }
        return memo[start];
    }
};

2. https://www.cnblogs.com/grandyang/p/4576240.html