C++ Trie Tree, works with each test case, but get runtime error when submit


  • 0
    class Solution {
        class TrieNode {
        public:
            TrieNode *child[26];
            bool isWord;
            TrieNode() {isWord = false;}
        };
    public:
        bool find(string word, TrieNode* root) {
            TrieNode* node = root;
            int i = 0;
            for(;i<word.size();i++) {
                int idx = word[i]-'a';
                if(node->child[idx]==nullptr) return false;
                node = node->child[idx];
            }
            return node->isWord;
        }
        bool dfs(string& word, TrieNode* root, int pos, int cnt) {
            //cout << word << ", " << pos << ", " << cnt << endl;
            if(cnt>1 && pos==word.size()) return true;
            for(int i=pos;i<word.size();i++) {
                string s = word.substr(pos,i-pos+1);
                if(!find(s,root)) continue;
                //cout << s << endl;
                cnt++;
                if(dfs(word,root,i+1,cnt)) return true;
                cnt--;
            }
            return false;
        }
        void deleteTree(TrieNode* root) {
            queue<TrieNode*> q;
            q.push(root);
            while(!q.empty()) {
                TrieNode* n = q.front();
                q.pop();
                for(int i=0;i<26;i++) {
                    if(n->child[i]!=nullptr) q.push(n->child[i]);
                }
                delete n;
            }
        }
        vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
            vector<string> ans;
            TrieNode* node = new TrieNode();
            TrieNode* tmp;
            for(string str:words) {
                tmp = node;
                for(char c:str) {
                    int idx = c-'a';
                    if(tmp->child[idx]==nullptr) tmp->child[idx] = new TrieNode();
                    tmp = tmp->child[idx];
                }
                tmp->isWord = true;
            }
            int cnt;
            for(int i=0;i<words.size();i++) {
                cnt = 0;
                if(dfs(words[i],node,0,cnt)) ans.push_back(words[i]);
            }
            deleteTree(node);
            return ans;
        }
    };
    

Log in to reply
 

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