Word Break

• Time : $O(B + |A|^2)$
• Space : $O(|B_i|)$

struct Trie {
    Trie* next[26];
    bool eof;
    Trie(): eof(false) {
        memset(next, 0, sizeof next);
    }
    
    void insert(string s, int p = 0) {
        if(p == s.length()) eof = true;
        else {
            if(!next[s[p]-'a']) next[s[p]-'a'] = new Trie();
            next[s[p]-'a']->insert(s,p+1);
        }
    }
};

int helper(Trie* root, string s, int p = 0) {
    if(p == s.length()) return true;
    Trie* runner = root;
    for(int i = p; i < s.length(); i++) {
        if(!runner->next[s[i]-'a']) return false;
        runner = runner->next[s[i]-'a'];
        if(runner->eof) {
            if(helper(root, s, i + 1)) return true;
        }
    }
    return false;
}

int Solution::wordBreak(string A, vector<string> &B) {
    Trie* t = new Trie();
    for(auto& b : B) t->insert(b);
    return helper(t,A);
}