Tries

Tries in Java

Tries (also known as prefix trees) are a fundamental data structure in Java and are widely used in Leetcode problems. A trie is a tree-like data structure that stores strings in a way that allows for efficient prefix-based searches.

Table of Contents

• Tries in Java
  • Table of Contents
  • Trie Basics
  • Common Trie Operations
    • 1. Inserting a Word
    • 2. Searching for a Word
    • 3. Checking if a Prefix Exists
  • Common Leetcode Patterns
    • 1. Prefix Search
    • 2. Word Search
    • 3. Autocomplete System
  • Time and Space Complexity
  • Related Leetcode Questions
    • Easy
    • Medium
    • Hard

Trie Basics

• Definition: A trie is a tree-like data structure that stores strings. Each node in the trie represents a character of a string, and the path from the root to a node represents a prefix of the string.
• Declaration:

  class TrieNode {
      TrieNode[] children = new TrieNode[26];
      boolean isEndOfWord;
  }

• Key Characteristics:
  • Efficient for prefix-based searches.
  • Each node has up to 26 children (for English alphabets).
  • The root node represents an empty string.

Common Trie Operations

1. Inserting a Word

• Example:

  public void insert(String word) {
      TrieNode current = root;
      for (char c : word.toCharArray()) {
          int index = c - 'a';
          if (current.children[index] == null) {
              current.children[index] = new TrieNode();
          }
          current = current.children[index];
      }
      current.isEndOfWord = true;
  }

• Time Complexity: O(m) (where m is the length of the word)
• Space Complexity: O(m)

2. Searching for a Word

• Example:

  public boolean search(String word) {
      TrieNode current = root;
      for (char c : word.toCharArray()) {
          int index = c - 'a';
          if (current.children[index] == null) {
              return false;
          }
          current = current.children[index];
      }
      return current.isEndOfWord;
  }

• Time Complexity: O(m) (where m is the length of the word)
• Space Complexity: O(1)

3. Checking if a Prefix Exists

• Example:

  public boolean startsWith(String prefix) {
      TrieNode current = root;
      for (char c : prefix.toCharArray()) {
          int index = c - 'a';
          if (current.children[index] == null) {
              return false;
          }
          current = current.children[index];
      }
      return true;
  }

• Time Complexity: O(m) (where m is the length of the prefix)
• Space Complexity: O(1)

Common Leetcode Patterns

1. Prefix Search

• Used for problems like implementing a trie, searching for words with a given prefix, etc.
• Example:

  Trie trie = new Trie();
  trie.insert("apple");
  boolean result = trie.search("apple");   // Returns true
  boolean result = trie.startsWith("app"); // Returns true

• Related Questions:
  • Implement Trie (Prefix Tree)
  • Design Add and Search Words Data Structure
  • Prefix and Suffix Search

2. Word Search

• Used for problems like word search in a grid, boggle game, etc.
• Example:

  public boolean exist(char[][] board, String word) {
      for (int i = 0; i < board.length; i++) {
          for (int j = 0; j < board[0].length; j++) {
              if (dfs(board, i, j, word, 0)) {
                  return true;
              }
          }
      }
      return false;
  }
  private boolean dfs(char[][] board, int i, int j, String word, int index) {
      if (index == word.length()) {
          return true;
      }
      if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(index)) {
          return false;
      }
      char temp = board[i][j];
      board[i][j] = '#';
      boolean found = dfs(board, i + 1, j, word, index + 1) ||
                      dfs(board, i - 1, j, word, index + 1) ||
                      dfs(board, i, j + 1, word, index + 1) ||
                      dfs(board, i, j - 1, word, index + 1);
      board[i][j] = temp;
      return found;
  }

• Related Questions:
  • Word Search
  • Word Search II

3. Autocomplete System

• Used for problems like designing an autocomplete system, suggesting words based on prefix, etc.

• Example:

  class AutocompleteSystem {
      private TrieNode root;
      private StringBuilder currentPrefix;
  
      public AutocompleteSystem(String[] sentences, int[] times) {
          root = new TrieNode();
          currentPrefix = new StringBuilder();
          for (int i = 0; i < sentences.length; i++) {
              insert(sentences[i], times[i]);
          }
      }
  
      public List<String> input(char c) {
          if (c == '#') {
              insert(currentPrefix.toString(), 1);
              currentPrefix.setLength(0);
              return new ArrayList<>();
          }
          currentPrefix.append(c);
          return search(currentPrefix.toString());
      }
  
      private void insert(String sentence, int times) {
          TrieNode current = root;
          for (char c : sentence.toCharArray()) {
              int index = c - 'a';
              if (current.children[index] == null) {
                  current.children[index] = new TrieNode();
              }
              current = current.children[index];
          }
          current.isEndOfWord = true;
          current.times += times;
      }
  
      private List<String> search(String prefix) {
          TrieNode current = root;
          for (char c : prefix.toCharArray()) {
              int index = c - 'a';
              if (current.children[index] == null) {
                  return new ArrayList<>();
              }
              current = current.children[index];
          }
          PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> a.times == b.times ? a.sentence.compareTo(b.sentence) : b.times - a.times);
          dfs(current, prefix, pq);
          List<String> result = new ArrayList<>();
          while (!pq.isEmpty() && result.size() < 3) {
              result.add(pq.poll().sentence);
          }
          return result;
      }
  
      private void dfs(TrieNode node, String prefix, PriorityQueue<Pair> pq) {
          if (node.isEndOfWord) {
              pq.add(new Pair(prefix, node.times));
          }
          for (int i = 0; i < 26; i++) {
              if (node.children[i] != null) {
                  dfs(node.children[i], prefix + (char) ('a' + i), pq);
              }
          }
      }
  
      class Pair {
          String sentence;
          int times;
          Pair(String sentence, int times) {
              this.sentence = sentence;
              this.times = times;
          }
      }
  }

• Related Questions:

  • Design Search Autocomplete System

Time and Space Complexity

Operation	Time Complexity	Space Complexity
Insert	O(m)	O(m)
Search	O(m)	O(1)
Starts With	O(m)	O(1)

Related Leetcode Questions

Easy

1. Implement Trie (Prefix Tree)
2. Design Add and Search Words Data Structure

Medium

1. Word Search
2. Word Search II
3. Design Search Autocomplete System

Hard

1. Prefix and Suffix Search
2. Concatenated Words
3. Maximum XOR of Two Numbers in an Array