class Solution {
public:

    struct vertex{
        bool leaf;
        map<char , int> to;
        vertex() {
            to.clear();
            leaf=0;
        }
    };

    bool wordBreak(string s, vector<string>& wordDict) {
        if (s.empty() || wordDict.empty()) return 0;
        vector<vertex> trie;
        trie.push_back(vertex());
        for (int i=0; i<wordDict.size(); i++){
            string ss = wordDict[i];
            int v=0;
            for (int j=0; j<ss.size(); j++){
                char c = ss[j];
                if (trie[v].to.count(c)==0){
                    trie.push_back(vertex());
                    trie[v].to[c] = trie.size()-1;
                }
                v = trie[v].to[c];
            }
            trie[v].leaf = 1;
        }
        int n = s.size();
        s = "#"+s;
        bool *dp = new bool[n+1];
        for (int i=1; i<=n; i++) dp[i]=0;
        dp[0]=1;
        for (int i=0; i<n; i++){
            if (dp[i]){

                int v=0, j = i+1;
                while (trie[v].to.count(s[j])>0) {
                   // cout << i << " " << j << " " << v << " " << trie[v].leaf << endl;
                    v = trie[v].to[s[j]];
                    dp[j]|=(trie[v].leaf);

                    j++;
                }


            }
        }
        return dp[n];



    }
};