Word Break - Part 2

Given a string s and a dictionary of words dict of length n, add spaces in s to construct a sentence where each word is a valid dictionary word. Each dictionary word can be used more than once. Return all such possible sentences.

Follow examples for better understanding.

• Time : O(s^2)
• Space : O(dict)

c++

struct Trie{
    Trie* next[26];
    bool eof = false;
    Trie() {
        memset(next, 0, sizeof(next));
    }
    void insert(string& s, int pos = 0) {
        if(pos == s.length()) eof = true;
        else {
            if(!next[s[pos]-'a']) next[s[pos]-'a'] = new Trie();
            next[s[pos]-'a']->insert(s, pos + 1);
        }
    }
    void query(Trie* root, string& s, string& build, vector<string>& res, int pos = 0) {
        if(pos == s.length()) {
            if(eof) res.push_back(build);
        } else {
            if(eof) {
                build.push_back(' ');
                root->query(root, s, build, res, pos);
                build.pop_back();
            }
            if(!next[s[pos]-'a']) return;
            build.push_back(s[pos]);
            next[s[pos]-'a']->query(root, s, build, res, pos + 1);
            build.pop_back();
        }
    }
};
class Solution{
public:
    vector<string> wordBreak(int n, vector<string>& dict, string s)
    {
        Trie* trie = new Trie();
        for(auto& dic : dict)
            trie->insert(dic);
        vector<string> res;
        trie->query(trie, s, string() = "", res);
        return res;
    }
};