My solution in C++


  • 0
    S
    #define SIZE 26
    class TrieNode {
    public:
        // Initialize your data structure here.
        TrieNode():terminable(false), node(0){
            memset(childNode, 0, sizeof(childNode));
        }
        TrieNode* childNode[SIZE];
        bool terminable;
    };
    
    class Index{
    public:
        int operator[](const char key){
            return key % 26;
        }
    };
    
    class Trie {
    public:
        Trie() {
            root = new TrieNode();
        }
    
        // Inserts a word into the trie.
        void insert(string s) {
            int size = s.size();
            TrieNode* cur = root;
            for(int i = 0; i < size; ++i){
                if(!cur->childNode[index[s[i]]]){
                    cur->childNode[index[s[i]]] = new TrieNode();
                    ++cur->node;
                }
                cur = cur->childNode[index[s[i]]];
            }
            cur->terminable = true;
        }
    
        // Returns if the word is in the trie.
        bool search(string key) {
            int size = key.size();
            TrieNode* cur = root;
            for(int i = 0; i < size; ++ i){
                if(!cur->childNode[index[key[i]]])
                    return false;
                cur = cur->childNode[index[key[i]]];
            }
            return cur->terminable;
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        bool startsWith(string prefix) {
            int size = prefix.size();
            TrieNode* cur = root;
            for(int i = 0; i < size; ++ i){
                if(!cur->childNode[index[prefix[i]]])
                    return false;
                cur = cur->childNode[index[prefix[i]]];
            }
            return true;
        }
    
    private:
        TrieNode* root;
        Index index;
    };

Log in to reply
 

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