Word Search in Trie in DSA Java

Mental Model

A trie stores words by sharing common prefixes, making it easy to check if a word exists by following its letters step-by-step.

Analogy: Imagine a tree of roads where each road sign is a letter. To find a word, you follow the signs letter by letter until you reach the end of the word.

root
 ↓
 a -> b -> c -> null
 ↓
 t (end)

Each arrow shows the next letter link in the trie.

Dry Run Walkthrough

Input: words: ["cat", "car", "bat"], search word: "car"

Goal: Check if the word "car" exists in the trie built from the given words.

Step 1: Insert "cat" into trie

root -> c -> a -> t[end]
root -> null

Why: Add letters c, a, t in sequence marking t as end of word

Step 2: Insert "car" into trie

root -> c -> a -> t[end]
               ↓
               r[end]
root -> null

Why: Reuse c and a nodes, add r node and mark as end

Step 3: Insert "bat" into trie

root -> c -> a -> t[end]
               ↓
               r[end]
root -> b -> a -> t[end]
root -> null

Why: Add new branch b -> a -> t for word "bat"

Step 4: Search for "car" letter by letter

root -> c -> a -> r[end]
root -> b -> a -> t[end]
root -> null

Why: Follow c, then a, then r nodes to find word

Step 5: Check if last node is end of word

Found 'r' node marked as end

Why: Confirm word "car" exists in trie

Result:

root -> c -> a -> r[end]
root -> b -> a -> t[end]
Word "car" found: true

Annotated Code

DSA Java

import java.util.*;

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

class Trie {
    private final TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode curr = root;
        for (char ch : word.toCharArray()) {
            curr.children.putIfAbsent(ch, new TrieNode()); // add node if missing
            curr = curr.children.get(ch); // move to next node
        }
        curr.isEndOfWord = true; // mark end of word
    }

    public boolean search(String word) {
        TrieNode curr = root;
        for (char ch : word.toCharArray()) {
            if (!curr.children.containsKey(ch)) {
                return false; // letter missing, word not found
            }
            curr = curr.children.get(ch); // move to next node
        }
        return curr.isEndOfWord; // check if end of word
    }
}

public class Main {
    public static void main(String[] args) {
        Trie trie = new Trie();
        String[] words = {"cat", "car", "bat"};
        for (String w : words) {
            trie.insert(w);
        }
        String searchWord = "car";
        System.out.println("Word '" + searchWord + "' found: " + trie.search(searchWord));
    }
}

curr.children.putIfAbsent(ch, new TrieNode()); // add node if missing

Add new node for letter if it does not exist

curr = curr.children.get(ch); // move to next node

Advance current node to child node for next letter

curr.isEndOfWord = true; // mark end of word

Mark last node as end of a valid word

if (!curr.children.containsKey(ch)) { return false; }

If letter missing in children, word does not exist

return curr.isEndOfWord; // check if end of word

Confirm current node marks end of searched word

Output

Word 'car' found: true

Complexity Analysis

Time: O(m) because we process each letter of the word once during insert and search, where m is word length

Space: O(n*m) in worst case for storing n words each of length m, but shared prefixes reduce space

vs Alternative: Compared to storing words in a list and searching linearly O(n*m), trie search is faster O(m)

Edge Cases

search word not in trie

search returns false because a letter is missing in children

DSA Java

if (!curr.children.containsKey(ch)) { return false; }

search empty string

returns false because root is not end of word

DSA Java

return curr.isEndOfWord;

insert duplicate words

duplicates do not create new nodes, end marker remains true

DSA Java

curr.isEndOfWord = true;

When to Use This Pattern

When you need to quickly check if a word or prefix exists among many words, use a trie to follow letters step-by-step for fast search.

Common Mistakes

Mistake: Not marking the last node as end of word after insertion
Fix: Set isEndOfWord = true on the last node after inserting all letters

Mistake: Returning true if prefix exists but not checking end of word
Fix: Return true only if current node is marked as end of word after search

Summary

Stores words letter by letter sharing prefixes for fast word search.

Use when you want to check if words exist quickly among many stored words.

The key is following letters stepwise and marking ends of words to distinguish full words from prefixes.

Practice

1. What is the main purpose of using a Trie data structure in word search problems?

easy

A. To perform arithmetic operations on words

B. To sort words alphabetically

C. To store words in a linked list

D. To efficiently store and search words by their prefixes

Solution

1. Step 1: Understand Trie structure

   A Trie stores characters of words in a tree-like structure where each node represents a character.

2. Step 2: Identify Trie usage in word search

   It allows quick prefix-based search, making it efficient to find words starting with given letters.

3. Final Answer:

   To efficiently store and search words by their prefixes -> Option D

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie is all about prefix-based fast word search [OK]

Common Mistakes:

• Confusing Trie with sorting data structures
• Thinking Trie stores words as linked lists
• Assuming Trie performs arithmetic on words

2. Which of the following is the correct way to declare a Trie node class in Java?

easy

A. class TrieNode { char val; TrieNode[] children = new TrieNode[26]; boolean isWord; }

B. class TrieNode { int val; TrieNode children; boolean isWord; }

C. class TrieNode { String val; TrieNode[] children = new TrieNode[26]; }

D. class TrieNode { char val; List<TrieNode> children; boolean isWord; }

Solution

1. Step 1: Check data types for Trie node

   Each node stores a character, an array of 26 children for letters a-z, and a boolean to mark word end.

2. Step 2: Validate options

   class TrieNode { char val; TrieNode[] children = new TrieNode[26]; boolean isWord; } matches this structure exactly with char val, TrieNode[] children of size 26, and boolean isWord.

3. Final Answer:

   class TrieNode { char val; TrieNode[] children = new TrieNode[26]; boolean isWord; } -> Option A

4. Quick Check:

   Correct TrieNode declaration = class TrieNode { char val; TrieNode[] children = new TrieNode[26]; boolean isWord; } [OK]

Hint: Trie nodes use char + array of 26 children + boolean flag [OK]

Common Mistakes:

• Using int or String instead of char for node value
• Using single child instead of array for children
• Using List instead of fixed-size array for children

3. What will be the output of the following Java code snippet that inserts words into a Trie and searches for "cat"?

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

class Trie {
  TrieNode root = new TrieNode();

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

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

public class Main {
  public static void main(String[] args) {
    Trie trie = new Trie();
    trie.insert("cat");
    trie.insert("car");
    System.out.println(trie.search("cat"));
    System.out.println(trie.search("cap"));
  }
}

medium

A. false
false

B. true
false

C. true
true

D. false
true

Solution

1. Step 1: Insert words "cat" and "car" into Trie

   Both words are inserted character by character, marking the last node's isWord as true.

2. Step 2: Search for "cat" and "cap"

   "cat" exists with isWord true, so search returns true. "cap" path is missing 'p' node, so returns false.

3. Final Answer:

   true false -> Option B

4. Quick Check:

   Inserted words found = true, missing word = false [OK]

Hint: Search returns true only if full word path and isWord true [OK]

Common Mistakes:

• Assuming partial prefix returns true
• Not marking isWord correctly on insert
• Confusing character indexing in children array

4. Identify the bug in the following Trie search method and choose the correct fix:

boolean search(String word) {
  TrieNode node = root;
  for (int i = 0; i <= word.length(); i++) {
    int idx = word.charAt(i) - 'a';
    if (node.children[idx] == null) return false;
    node = node.children[idx];
  }
  return node.isWord;
}

medium

A. Initialize idx before loop

B. Return true inside the loop

C. Change loop condition to i < word.length()

D. Remove return statement inside loop

Solution

1. Step 1: Analyze loop boundary

   The loop runs from i = 0 to i <= word.length(), which causes index out of bounds at last iteration.

2. Step 2: Fix loop condition

   Changing condition to i < word.length() prevents accessing invalid index and correctly iterates over characters.

3. Final Answer:

   Change loop condition to i < word.length() -> Option C

4. Quick Check:

   Loop boundary fix prevents index error [OK]

Hint: Loop over string chars with i < length, not <= length [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Trying to fix by moving idx initialization
• Removing return inside loop causing wrong logic

5. Given a 2D board of characters and a list of words, which approach best uses a Trie to efficiently find all words present on the board? A sample board:

[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Words: ["oath", "pea", "eat", "rain"]

hard

A. Build a Trie from words, then DFS on board checking prefixes in Trie

B. Check each word by scanning entire board without Trie

C. Use a hash set for words and scan board rows only

D. Sort words and board rows, then binary search each word

Solution

1. Step 1: Build Trie from given words

   Insert all words into a Trie to enable prefix checking during search.

2. Step 2: Perform DFS on board cells

   From each cell, explore neighbors recursively, checking if current path matches any prefix in Trie to prune search.

3. Step 3: Collect words found when Trie node marks word end

   This approach efficiently finds all words without redundant searches.

4. Final Answer:

   Build a Trie from words, then DFS on board checking prefixes in Trie -> Option A

5. Quick Check:

   Trie + DFS = efficient word search on board [OK]

Hint: Use Trie for prefix pruning during DFS on board [OK]

Common Mistakes:

• Searching words one by one scanning whole board
• Ignoring prefix pruning causing slow search
• Using sorting and binary search which doesn't fit 2D board