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:

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;
  }
}

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.