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

How to 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.

Time complexity to build trie data structure is $\text{O(N)}$, where $\text{N}$ represents the total number of characters in all the words within a string array.

Below is tree representation of a tries data structure:

Java

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

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

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

  public void insert(String str) {
    TrieNode current = root;
    for(int i = 0; i < str.length(); i++) {
      char ch = str.charAt(i)
      if(!current.children.containsKey(ch)) current.children.put(ch, new TrieNode());
      current = current.children.get(ch);
    }
    current.isWord = true;
  }
}

How to Use Tries

A Trie data structure can be used to check if a given word exists or if a prefix of the word is present in the Trie.

Java

// Search for a word in the Trie
public boolean search(String word) {
  TrieNode current = root;
  for(char ch: word) {
    if(!current.children.containeKey(ch)) return false;
    current = current.children.get(ch);
  }
  return current.isWord;
}

// check if a prefix exists in the Trie
public boolean startsWith(String prefix) {
  TrieNode current = root;
  for(char ch: prefix) {
    if(!current.children.containsKey(ch)) return false;
    current = current.children.get(ch);
  }
  return true;
}

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