LIKE CODING: MJ [44] Find the Longest Substring

LIKE CODING: MJ [44] Find the Longest Substring
Give a dictionary "dict" and a string "S", find the longest valid word in dict which is a substring of "S".
Eg. dict = {"abc", "defgh", "ef"}
       S = "adbecfgh".
It should return "defgh".

class TrieNode{

public:

    char key;

    bool isLeaf = false;

    TrieNode * children[26] = {NULL};

    TrieNode(){}

    TrieNode(char k):key(k){}

};

 

class Solution{

    TrieNode *root = new TrieNode();

    void insert(string s){

        TrieNode *p = root;

        for(auto c:s){

            if(p->children[c-'a']==NULL){

                p->children[c-'a'] = new TrieNode(c);

            }

            p = p->children[c-'a'];

        }

        p->isLeaf = true;

    }

public:

    string longestString(vector<string> &dict, string S){

        for(auto s:dict) insert(s);

        int sz = S.size();

        string ret;

        bt(0, sz, S, root, ret, "");

        return ret;

    }

    void bt(int pos, int sz, string &S, TrieNode *t, string &ret, string cur){

        if(t->isLeaf && cur.size()>ret.size()){

            ret = cur;

        }

        if(pos<sz){

            for(int i = pos; i<sz; ++i){

                char c = S[i];

                if(t->children[c-'a']){

                    bt(i+1, sz, S, t->children[c-'a'], ret, cur+c);

                }

            }

        }

    }

};

http://www.mitbbs.com/article_t/JobHunting/32960525.html
Read full article from LIKE CODING: MJ [44] Find the Longest Substring