C++ using hash and DFS


  • 0
    class Solution {
    private:
        unordered_map<string,vector<string>> hash;
    public:
        vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
            vector<string> res;
            if(s.empty()) {
                return {""};
            }
            for(string word : wordDict) {
                int l = word.size();
                if((int)s.find(word,0)==0) {
                    string remStr = s.substr(l);
                    if(hash.count(remStr)==0) hash[remStr] = wordBreak(s.substr(l),wordDict);
                    for(string str : hash[remStr]) {
                        if(str!="") res.push_back(word+" "+str);
                        else res.push_back(word);
                    }
                }
            }
            return res;
        }
    };
    

Log in to reply
 

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