An Accepted Solution but Quite Slow, Anyone Can Help?


  • 0
    Y
    class TrieNode {
    public:
        char charValue;
        unordered_map<char,TrieNode*> child;
        bool isEnd;
        bool hasChild;
        // Initialize your data structure here.
        TrieNode() {
            isEnd = false;
            hasChild = false;
        }
        TrieNode(char ch) {
            charValue = ch;
            isEnd = false;
            hasChild = false;
        }
    };
    
    class Trie {
    public:
        Trie() {
            root = new TrieNode();
        }
    
        // Inserts a word into the trie.
        void insert(string word) {
            TrieNode* head = root;
            for(int i = 0; i < word.length(); i++) {
                if(head->child[word[i]] == NULL) {
                    TrieNode* ch = new TrieNode(word[i]);
                    head->child[word[i]] = ch;
                }
                head->hasChild = true;
                head = head->child[word[i]];
                if(i == word.length() - 1) head->isEnd = true;
            }
        }
    
        // Returns if the word is in the trie.
        bool search(string word) {
            TrieNode* head = root;
            for(int i = 0; i< word.length(); i++) {
                if(head->child[word[i]] == NULL) return false;
                if(head->isEnd && (i < word.length() - 1)) {
                    if(head->hasChild) {
                        head = head->child[word[i]];
                        continue;
                    } else return false;
                }
                head = head->child[word[i]];
            }
            if(head->isEnd == false) return false;
            return true;
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        bool startsWith(string prefix) {
            TrieNode* head = root;
            for(int i = 0; i< prefix.length(); i++) {
                if(head->child[prefix[i]] == NULL) return false;
                if(head->isEnd && (i < prefix.length() - 1)) {
                    if(head->hasChild) {
                        head = head->child[prefix[i]];
                        continue;
                    } else return false;
                }
                head = head->child[prefix[i]];
            }
            return true;
        }
    
    private:
        TrieNode* root;
    };

  • 0
    S

    search & startWith can share a helper method to search a String and return the last TrieNode


Log in to reply
 

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