Implement Trie (Prefix Tree)

---

Implement Trie (Prefix Tree): A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

• Trie() Initializes the trie object.
• void insert(String word) Inserts the string word into the trie.
• boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
• boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example 1:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

---

Constraints:

• 1 <= word.length, prefix.length <= 2000
• word and prefix consist only of lowercase English letters.
• At most 3 * 10^4 calls in total will be made to insert, search, and startsWith.

---

Try this Problem on your own or check similar problems:

1. Design Add and Search Words Data Structure
2. Replace Words
3. Encrypt and Decrypt Strings

Solution:

Java

class Trie {
  private class TrieNode{
      TrieNode[] children;
      boolean isWord = false;
      public TrieNode(){
          children = new TrieNode[26];
      }
  }

  TrieNode root;
  public Trie() {
      root = new TrieNode();
  }

  private TrieNode searchPrefix(String prefix){
      TrieNode iter = root;
      for(int i = 0; i < prefix.length(); ++i){
          char letter = prefix.charAt(i);
          if(iter.children[letter - 'a'] == null){
              return null;
          }
          iter = iter.children[letter - 'a'];
      }
      return iter;
  }

  public void insert(String word) {
      TrieNode iter = root;
      for(int i = 0; i < word.length(); ++i){
          char letter = word.charAt(i);
          if(iter.children[letter - 'a'] == null){
              iter.children[letter - 'a'] = new TrieNode();
          }
          iter = iter.children[letter - 'a'];
      }
      iter.isWord = true;
  }

  public boolean search(String word) {
      TrieNode node = searchPrefix(word);
      return node != null && node.isWord;
  }

  public boolean startsWith(String prefix) {
      return searchPrefix(prefix) != null;
  }
}

JavaScript

var Trie = function () {
  this.root = new TrieNode();
};

/**
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function (word) {
  let iter = this.root;
  for (let i = 0; i < word.length; ++i) {
    const letter = word.charAt(i);
    if (!iter.children[letter]) {
      iter.children[letter] = new TrieNode();
    }
    iter = iter.children[letter];
  }
  iter.isWord = true;
};

/**
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function (word) {
  const node = this.searchPrefix(word);
  return node !== null && node.isWord;
};

/**
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function (prefix) {
  return this.searchPrefix(prefix) !== null;
};

Trie.prototype.searchPrefix = function (prefix) {
  let iter = this.root;
  for (let i = 0; i < prefix.length; ++i) {
    const letter = prefix.charAt(i);
    if (!iter.children[letter]) {
      return null;
    }
    iter = iter.children[letter];
  }
  return iter;
};

class TrieNode {
  constructor() {
    this.children = {};
    this.isWord = false;
  }
}

/**
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */

Python

class Trie:
    def __init__(self):
      self.root = TrieNode()

    def searchPrefix(self, prefix):
        iter = self.root
        for letter in prefix:
            if letter not in iter.children:
                return None
            iter = iter.children[letter]
        return iter


    def insert(self, word: str) -> None:
        iter = self.root
        for letter in word:
            if letter not in iter.children:
                iter.children[letter] = TrieNode()
            iter = iter.children[letter]
        iter.isWord = True


    def search(self, word: str) -> bool:
      node = self.searchPrefix(word)
      return node is not None and node.isWord


    def startsWith(self, prefix: str) -> bool:
      return self.searchPrefix(prefix) is not None

class TrieNode:
    def __init__(self):
        self.children = {}
        self.isWord = False

# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

C++

class Trie {
class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    bool isWord;

    TrieNode() {
        isWord = false;
    }
};
private:
  TrieNode* root;

public:
    Trie() {
      root = new TrieNode();
    }

    TrieNode* searchPrefix(string prefix) {
        TrieNode* iter = root;
        for (char letter : prefix) {
            if (iter->children.find(letter) == iter->children.end()) {
                return nullptr;
            }
            iter = iter->children[letter];
        }
        return iter;
    }

    void insert(string word) {
        TrieNode* iter = root;
        for (char letter : word) {
            if (iter->children.find(letter) == iter->children.end()) {
                iter->children[letter] = new TrieNode();
            }
            iter = iter->children[letter];
        }
        iter->isWord = true;
    }

    bool search(string word) {
        TrieNode* node = searchPrefix(word);
        return node != nullptr && node->isWord;
    }

    bool startsWith(string prefix) {
        return searchPrefix(prefix) != nullptr;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

---

Time/Space Complexity:

• Time Complexity: O(sum(w)) where sum(w) sum of lengths of all inserted words
• Space Complexity: O(sum(w))

---

Explanation:

You can think of trie as a k-ary search tree where each node can have k children, in this case each TrieNode can have 26 children (since we only deal with lowercase English letters), also note that each TrieNode holds the information isWord which indicates that current node is the end letter of the inserted word. At the Trie constructor we define the root which will be the entry point for both read and writes to the trie. For inserting the word, we start with our root and check if it has child at index corresponding to the first letter in the word letter - 'a', if not we create it (with its set of children), then we move to that new node following the edge that matches the first letter. We follow the same pattern for all other letters of the word we're inserting into the trie. The same goes for search and startsWith we utilize the searchPrefix method which will traverse the trie and return the TrieNode matching the last letter in the prefix, note that for startsWith it is enough to just check if the returned node is not null, but for search(word) we also have to check node.isWord flag.