Trie vs Hash Map for Prefix Matching in DSA Java - Build Both Approaches

Trie vs Hash Map for Prefix Matching

📖 Scenario: Imagine you are building a simple search feature for a phone contacts app. You want to find all contacts whose names start with a certain prefix quickly. Two common ways to do this are using a Trie (a special tree for words) or a Hash Map (a dictionary that stores words).

🎯 Goal: You will create a small list of contact names, then write code to find all contacts starting with a given prefix using both a Trie and a Hash Map. This will help you see how each method works for prefix matching.

📋 What You'll Learn

Create a list of contact names exactly as given

Create a prefix string to search for

Implement prefix matching using a Trie data structure

Implement prefix matching using a Hash Map filtering

Print the results of both methods

💡 Why This Matters

🌍 Real World

Phone contacts apps, autocomplete search bars, and dictionary word lookups often need to find words starting with a prefix quickly.

💼 Career

Understanding Tries and Hash Maps for prefix matching is useful for software engineers working on search features, autocomplete, and text processing.

1

Create the contact list

Create a List<String> called contacts with these exact names: "Alice", "Bob", "Alfred", "Brenda", "Albert"

DSA Java

// Create the contacts list with given names
// Your code here

Hint

Use Arrays.asList to create the list with the exact names.

2

Create the prefix to search

Create a String variable called prefix and set it to "Al"

DSA Java

import java.util.*;

public class PrefixMatching {
    public static void main(String[] args) {
        List contacts = Arrays.asList("Alice", "Bob", "Alfred", "Brenda", "Albert");
        // Create the prefix string
        // Your code here
    }
}

Hint

Use String prefix = "Al"; to create the prefix.

3

Implement prefix matching using Trie and Hash Map

Add a static inner class TrieNode with a Map<Character, TrieNode> called children and a boolean isWord. Then add methods insert(String word) and List<String> searchPrefix(String prefix) to insert words and find all words starting with prefix. Also, create a List<String> called hashMapResult that stores all contacts starting with prefix using startsWith. Use contacts and prefix from previous steps.

DSA Java

import java.util.*;

public class PrefixMatching {
    static class TrieNode {
        Map children = new HashMap();
        boolean isWord = false;
    }

    static class Trie {
        TrieNode root = new TrieNode();

        // Add insert and searchPrefix methods here
        // Your code here
    }

    public static void main(String[] args) {
        List contacts = Arrays.asList("Alice", "Bob", "Alfred", "Brenda", "Albert");
        String prefix = "Al";

        // Build Trie and find prefix matches
        // Also find prefix matches using Hash Map filtering
        // Your code here
    }
}

Hint

Define the TrieNode and Trie classes with insert and searchPrefix methods. Use a loop to insert contacts into the Trie. Use startsWith to filter contacts for the Hash Map method.

4

Print the results of prefix matching

Print the lists trieResult and hashMapResult exactly as shown: System.out.println("Trie result: " + trieResult); and System.out.println("Hash Map result: " + hashMapResult);

DSA Java

import java.util.*;

public class PrefixMatching {
    static class TrieNode {
        Map children = new HashMap();
        boolean isWord = false;
    }

    static class Trie {
        TrieNode root = new TrieNode();

        void insert(String word) {
            TrieNode node = root;
            for (char ch : word.toCharArray()) {
                node = node.children.computeIfAbsent(ch, c -> new TrieNode());
            }
            node.isWord = true;
        }

        List searchPrefix(String prefix) {
            List results = new ArrayList();
            TrieNode node = root;
            for (char ch : prefix.toCharArray()) {
                node = node.children.get(ch);
                if (node == null) {
                    return results; // empty list
                }
            }
            collectAllWords(node, new StringBuilder(prefix), results);
            return results;
        }

        void collectAllWords(TrieNode node, StringBuilder prefix, List results) {
            if (node.isWord) {
                results.add(prefix.toString());
            }
            for (Map.Entry entry : node.children.entrySet()) {
                prefix.append(entry.getKey());
                collectAllWords(entry.getValue(), prefix, results);
                prefix.deleteCharAt(prefix.length() - 1);
            }
        }
    }

    public static void main(String[] args) {
        List contacts = Arrays.asList("Alice", "Bob", "Alfred", "Brenda", "Albert");
        String prefix = "Al";

        Trie trie = new Trie();
        for (String contact : contacts) {
            trie.insert(contact);
        }

        List trieResult = trie.searchPrefix(prefix);

        List hashMapResult = new ArrayList();
        for (String contact : contacts) {
            if (contact.startsWith(prefix)) {
                hashMapResult.add(contact);
            }
        }

        // Print the results
        // Your code here
    }
}

Hint

Use System.out.println to print the lists exactly as shown.

Practice

1. Which data structure is generally more efficient for prefix matching in a large set of strings?

easy

A. Array, because it stores elements in order and allows binary search

B. Trie, because it stores characters in a tree structure allowing fast prefix search

C. Hash Map, because it stores keys with direct access and no traversal

D. Linked List, because it allows sequential access to all elements

Solution

1. Step 1: Understand prefix matching requirement

   Prefix matching means finding all strings starting with a given prefix quickly.

2. Step 2: Compare Trie and Hash Map for prefix search

   Trie stores characters in nodes linked by edges, allowing traversal by prefix. Hash Map requires checking all keys or storing prefixes separately, which is less efficient.

3. Final Answer:

   Trie, because it stores characters in a tree structure allowing fast prefix search -> Option B

4. Quick Check:

   Trie = Fast prefix search [OK]

Hint: Trie is designed for prefix search, hash map is not [OK]

Common Mistakes:

• Thinking hash map can do prefix search directly
• Confusing array or linked list with prefix search efficiency

2. Which of the following is the correct way to check if a prefix exists in a Trie in Java?

easy

A. Use a loop to traverse nodes for each character of the prefix and check if nodes exist

B. Use HashMap.containsKey(prefix) directly on the Trie root

C. Use binary search on the Trie nodes array

D. Use recursion to check if prefix is a substring of any word

Solution

1. Step 1: Understand Trie prefix search method

   To check prefix, we traverse the Trie nodes character by character along the prefix path.

2. Step 2: Evaluate options for prefix check

   Use a loop to traverse nodes for each character of the prefix and check if nodes exist correctly describes traversal. Use HashMap.containsKey(prefix) directly on the Trie root is incorrect because HashMap.containsKey checks full keys, not prefixes. Use binary search on the Trie nodes array and D do not apply to Trie structure.

3. Final Answer:

   Use a loop to traverse nodes for each character of the prefix and check if nodes exist -> Option A

4. Quick Check:

   Traverse nodes for prefix = Use a loop to traverse nodes for each character of the prefix and check if nodes exist [OK]

Hint: Traverse Trie nodes for each prefix character [OK]

Common Mistakes:

• Using HashMap.containsKey for prefix check
• Trying binary search on Trie nodes
• Confusing substring with prefix

3. Given the following Java Trie code snippet, what will be the output after inserting words "cat", "car", "dog" and checking prefix "ca"?

Trie trie = new Trie();
trie.insert("cat");
trie.insert("car");
trie.insert("dog");
boolean result = trie.startsWith("ca");
System.out.println(result);

medium

A. Compilation error

B. false

C. true

D. Runtime exception

Solution

1. Step 1: Insert words into Trie

   Words "cat", "car", and "dog" are inserted, creating nodes for 'c', 'a', 't', 'r', 'd', 'o', 'g'.

2. Step 2: Check prefix "ca"

   Prefix "ca" matches nodes 'c' and 'a' in the Trie, so startsWith returns true.

3. Final Answer:

   true -> Option C

4. Quick Check:

   Prefix "ca" exists = true [OK]

Hint: Inserted words with prefix "ca" means startsWith("ca") is true [OK]

Common Mistakes:

• Assuming startsWith returns false if prefix is not a full word
• Confusing startsWith with search for full word
• Expecting compilation or runtime errors

4. Consider this Java code snippet using a HashMap to store words and check prefixes:

HashMap map = new HashMap<>();
map.put("apple", true);
map.put("app", true);
boolean prefixExists = map.containsKey("ap");
System.out.println(prefixExists);

What is the output and why?

medium

A. false, because "ap" is not a key in the map

B. true, because "ap" is a prefix of "app" and "apple"

C. Compilation error due to wrong HashMap usage

D. Runtime exception due to null key

Solution

1. Step 1: Understand HashMap key storage

   HashMap stores exact keys "apple" and "app", but not "ap".

2. Step 2: Check containsKey("ap")

   containsKey checks for exact key match, so returns false for "ap".

3. Final Answer:

   false, because "ap" is not a key in the map -> Option A

4. Quick Check:

   HashMap exact key check = false for "ap" [OK]

Hint: HashMap keys must match exactly, no prefix matching [OK]

Common Mistakes:

• Assuming containsKey checks prefixes
• Expecting true because "ap" is prefix of stored keys
• Confusing HashMap with Trie behavior

5. You need to implement a system that supports fast prefix queries on millions of words and also allows quick insertion and deletion. Which data structure is best suited and why?

hard

A. ArrayList, because it allows fast insertion and deletion at the end

B. Hash Map, because it provides constant time insertion and deletion

C. Balanced Binary Search Tree, because it keeps data sorted for prefix search

D. Trie, because it supports efficient prefix queries and dynamic updates

Solution

1. Step 1: Analyze prefix query requirement

   Fast prefix queries require a data structure that can traverse prefixes efficiently.

2. Step 2: Compare data structures for insertion, deletion, and prefix search

   Trie supports prefix queries efficiently and allows insertion/deletion by node updates. Hash Map is fast for exact keys but not prefix queries. Balanced BST supports sorted data but prefix search is slower. ArrayList is inefficient for prefix queries and deletions.

3. Final Answer:

   Trie, because it supports efficient prefix queries and dynamic updates -> Option D

4. Quick Check:

   Trie = best for prefix queries + updates [OK]

Hint: Trie handles prefix queries and updates efficiently [OK]

Common Mistakes:

• Choosing Hash Map for prefix queries
• Assuming balanced BST is best for prefix search
• Ignoring deletion complexity in ArrayList