Data Structures

Trie

class Node { public: Node* children[26]; bool endOfWord;

`Node()`
`{`
    `endOfWord = false;`
    `for(int i=0; i< 26; i++)`
    `{`
        `children[i] = NULL;`
    `}`
`}`

};

class Trie { public:

`Node root;`

`/** Initialize your data structure here. */`
`Trie() {`
    `root = Node();`
`}`

`/** Adds a word into the data structure. */`
`void addWord(string word) {`
    
    `Node* curr = &root;`
    
    `for(int i=0; i<word.length(); i++)`
    `{`
        `Node* child = (curr->children)[word[i]-'a'];`
        `if(child==NULL)`
        `{`
            `Node *newNode = new Node();`
            `(curr->children)[word[i]-'a'] = newNode;`
            `curr = newNode;`
        `}`
        `else`
        `{`
            `curr = child;`
        `}`
    `}`
    
    `curr->endOfWord = true;`
`}`

`bool search(string word) {`
    `Node* curr = &root;`
    `for(int i=0; i<word.length(); i++)`
    `{`
        `Node* child = (curr->children)[word[i]-'a'];`
        `if(child==NULL)`
        `{`
            `return false;`
        `}`
        `else`
        `{`
            `curr = child;`
        `}`
    `}`
    `return curr->endOfWord;`
`}`

};