C++ Code Using Trie + BFS


  • 0
    D

    Most of codes using trie here are searching with DFS, I would like to do it with no-recursion BFS. Well I saw a previous post saying that BFS will result in TLE. I don't think BFS will have a higher time complexity compared with DFS. I just return the result (true or false) when I find a solution in the current search process, without traverse all the nodes in the queue.

    class TrieNode {
    public:
        char c;
        bool is_word;
        unordered_map<char, TrieNode*> children;
        TrieNode() {
            is_word = false;
        }
        TrieNode(char input) {
            c = input;
            is_word = false;
        }
    };
    
    class WordDictionary {
    private:
        TrieNode* root;
    public:
        WordDictionary() {
            root = new TrieNode();
        }
        
        void addWord(string word) {
            TrieNode* cur = root;
            for (int i = 0; i < word.length(); i++) {
                if (cur->children.find(word[i]) != cur->children.end()) {
                    // go deeper
                    cur = cur->children[word[i]];
                } else {
                    // creat new node
                    TrieNode* node_new = new TrieNode(word[i]);
                    cur->children[word[i]] = node_new;
                    cur = node_new;
                }
            }
            cur->is_word = true;
        }
    
        bool search(string word) {
            queue<TrieNode*> q;
            q.push(root);
            int pos_next = 0;
            bool found = false;
    
            while (!q.empty()) {
                int size = q.size();
                for (int i = 0; i < size; i++) {
                    TrieNode* cur = q.front();
                    q.pop();
                    if (word[pos_next] == '.') {
                        for (auto& i : cur->children) {
                            q.push(i.second);
                            // check is word or not
                            if (pos_next == word.length() - 1) {
                                if ((i.second)->is_word) {
                                    return true;
                                }
                            }
                        }
                    } else {
                        // have char
                        if (cur->children.find(word[pos_next]) != cur->children.end()) {
                            q.push(cur->children[word[pos_next]]);
                            if (pos_next == word.length() - 1) {
                                if ((cur->children[word[pos_next]])->is_word) {
                                    return true;
                                }
                            }
                        }
                    }
                }
                pos_next++;
            }
            return false;
        }
    };
    

Log in to reply
 

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