Tries

This page provides links to solutions for problems that use the Tries data structure.

Overview

A Trie is a tree-like data structure used to store strings efficiently.

• Each node in the tries represents a single character.
• A path from the root to node represent a prefix of stored strings.
• The end of word is typically marked by a special flag.

Build Tries

Let's build a tries data structure for below string array:

$$\text{arr} = \begin{bmatrix} \text{app, ape, bat, cat} \end{bmatrix}$$

We will start by creating a TrieNode class to represent each node. Each node will store its children, organized as a map or an array for character to node mapping, along with a flag to indicate whether the node represents the end of a word.

Java

import java.util.HashMap;
import java.util.Map;

class TrieNode {
  Map<Character, TrieNode> children = new HashMap<>();
  boolean isWord = false; 
}

We start by creating a root node, which serves as the first trie and represents the beginning of any word.

We then begin adding each word from the string array into the trie object. After adding the word 'app', the trie appears as follows:

After adding the word 'ape', the trie appears as follows:

After adding the word 'bat', the trie appears as follows:

After adding the word 'cat', the trie appears as follows:

Java

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

  public void insert(String str) {
    TrieNode current = root;
    // for each character in a string
    for(int i = 0; i < str.length(); i++) {
      char ch = str.charAt(i)
      // check if chracter at index 'i', is present in current trie node 
      // if not add add character to current trie node's map 
      if(!current.children.containsKey(ch)) current.children.put(ch, new TrieNode());
      // move to next node
      current = current.children.get(ch);
    }
    // flag end of word
    current.isWord = true;
  }
}

Use Tries

Let's search for the word 'ape' in the trie. We begin at the root node and check if the first character, 'a', exists in the root node's hashmap.

Since the character 'a' exists, we move to the next node 'a' and look for the second character, 'p'.

Again, the character 'p' exists, we move to the next node 'p' and look for the second character, 'e'.

We then move to the last character of the word, 'e', and look for it in the next node.

At this point, we have found all the characters from the word 'ape' in the trie. Now, we have two options:

• If we were looking for the prefix 'ape', we return true.
• If we were looking for the full word 'ape', we check the current node to see if it flags the end of the word. If it does, we return true; otherwise, we return false.

In this case, the current node 'e' flags the end of the word in the trie, so we return true.

Java

// search for a word or prefix in the Trie
public boolean search(String word, boolean lookingPrefix) {
  TrieNode current = root;
  for(char ch: word) {
    // if next character not found in the current node's hashmap
    if(!current.children.containeKey(ch)) return false;
    current = current.children.get(ch);
  }
  return lookingPrefix ? lookingPrefix : current.isWord;
}

Complexity

Let's say there are total $\text{N}$ characters in all the words within a string array.

Time Complexity

Time complexity for building tries data structure is:

$$\text{O(N)}$$

Time complexity for searching a word of length $\text{M}$ in a tries data structure is:

$$\text{O(M)}$$

Space Complexity

Space complexity of tries is:

$$\text{O(N) * Average space required for HashMap}$$

Where $\text{Average space required for HashMap}$ is propotional to number of characters allowed in a string array.

How to Spot These Problems

You can identify trie problems if the problem requires you to:

• Efficiently search for words or prefixes within a large dataset.
• Implement auto-complete or auto-suggestion functionality.
• Find words that share a common prefix.
• Count the number of words with a specific prefix.
• Solve problems involving substring or pattern matching in text.

Leetcode Problem Set