Tree

Trie (Prefix Tree)

[Medium] No.208 Implement Trie (Prefix Tree)

[Medium] 211. Add and Search Word - Data structure design

Trie node structure:

struct TrieNode { bool flag; // 'true': when the string is at the end, otherwise it's false map<char, TrieNode*> next; // You can use a vector to replace the map };

Insertion of a key in a trie:

(The above image is from leetcode.com.)

Time Complexity: O(N), where N is the key length.

Space Complexity: O(N), the worst case is to insert every single letter of key.

class Trie { public: /** Initialize your data structure here. */ TrieNode* root; Trie() { root = new TrieNode(); } /** Inserts a word into the trie. */ void insert(string word) { TrieNode* p = root; // empty root for(int i = 0 ; i < word.size() ; i++){ if( (p->next).count(word[i]) <= 0){ // prefix does not exist //insert prefix (p->next).insert({word[i], new TrieNode()}); } //move on to the next trienode p = (p->next)[word[i]]; } //mark the position which ends the string p->flag = true; } };

Search for a key in a trie:

(The above image is from leetcode.com.)

Time Complexity: O(N), where N is the number of nodes in the given list.

Space Complexity: O(1)

class Trie { public: /** Initialize your data structure here. */ TrieNode* root; Trie() { root = new TrieNode(); } /** Returns if the word is in the trie. */ bool search(string word) { TrieNode* iter = root; for(int i = 0 ; i < word.size() ; i++){ if( (iter->next).count(word[i]) <= 0){ return false; } iter = iter->next[word[i]]; } return iter->flag; //if the target string ends but the flag isn't true, meaning that we don't have matched string in the map } };

Search for a key prefix in a trie:

(The above image is from leetcode.com.)

Time Complexity: O(N), where N is the number of nodes in the given list.

Space Complexity: O(1)

class Trie { public: /** Initialize your data structure here. */ TrieNode* root; Trie() { root = new TrieNode(); } /** Returns if there is any word in the trie that starts with the given prefix. */ bool startsWith(string prefix) { TrieNode* iter = root; for(int i = 0 ; i < prefix.size() ; i++){ if( (iter->next).count(prefix[i]) <= 0){ return false; } iter = iter->next[prefix[i]]; } return true; //we only care about whether we have the same prefix in the map, not the whole same string in the map } };