Interview AiBox logo
Interview AiBox
#208
Medium
auto_awesomeHash Table plus String

LeetCode Problem Workspace

Implement Trie (Prefix Tree)

This problem requires designing a Trie (Prefix Tree) to efficiently store and query strings using hash table concepts for fast retrieval.

hash tablestringdesigntrie
category

4

Topics

code_blocks

8

Code langs

hub

3

Related

play_arrowStart Solutionarrow_forward
speedComplexityopen_in_newLeetCode

Practice Focus

Medium · Hash Table plus String

bolt

Answer-first summary

This problem requires designing a Trie (Prefix Tree) to efficiently store and query strings using hash table concepts for fast retrieval.

Interview AiBox logo

Ace coding interviews with Interview AiBox guidance for Hash Table plus String

Try AiBox Copilotarrow_forward

Start by defining a TrieNode class with a hashmap for children and a flag for word completion. Insert words by traversing or creating nodes for each character. Search operations check the path character by character, and prefix queries verify the presence of a path without requiring full word matches, ensuring both time and space efficiency for up to 2000-character strings.

Problem Statement

Implement a Trie (Prefix Tree) that supports inserting words, searching for full words, and checking if any words start with a given prefix. The Trie should efficiently handle string storage and retrieval using a hash map for children nodes.

Design the Trie class with the following methods: insert(word) to store a string, search(word) to check if the word exists, and startsWith(prefix) to verify if any stored word begins with the given prefix. The Trie should support up to 3 * 10^4 operations, and words or prefixes contain only lowercase English letters up to length 2000.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Input ["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]] Output [null, null, true, false, true, null, true]

Explanation Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // return True trie.search("app"); // return False trie.startsWith("app"); // return True trie.insert("app"); trie.search("app"); // return True

Constraints

  • 1 <= word.length, prefix.length <= 2000
  • word and prefix consist only of lowercase English letters.
  • At most 3 * 104 calls in total will be made to insert, search, and startsWith.

Solution Approach

Node Structure with Hash Map

Create a TrieNode class that stores child nodes in a hash map keyed by characters, and include a boolean flag indicating whether the node completes a valid word. This ensures O(1) child access per character.

Insert Method Traversal

Traverse the Trie character by character. For each character, check if it exists in the current node's hash map; if not, create a new node. Mark the last node as a completed word to differentiate full words from prefixes.

Search and Prefix Queries

To search, traverse nodes according to the characters and check the end-of-word flag for full words. For startsWith, traverse the prefix characters only and return true if the path exists, regardless of the end-of-word flag.

Complexity Analysis

Metric Value
Time Depends on the final approach
Space Depends on the final approach

Insertion, search, and prefix checks take O(L) time, where L is the length of the word or prefix, because each character requires a hash map lookup. Space is O(N * L) in the worst case, storing N words of length L, though shared prefixes reduce overall memory usage.

What Interviewers Usually Probe

  • They may ask about handling large alphabets efficiently with hash maps.
  • Expect questions on optimizing space with shared nodes or array-based children.
  • They often probe edge cases like empty strings or maximum-length words.

Common Pitfalls or Variants

Common pitfalls

  • Forgetting to mark the end-of-word flag, causing search to fail on full words.
  • Using arrays instead of hash maps in languages with sparse character sets, wasting space.
  • Confusing prefix checks with full word checks, returning incorrect results for startsWith.

Follow-up variants

  • Implement a Trie that supports deletion of words while maintaining prefix correctness.
  • Extend the Trie to store frequencies or counts for autocomplete ranking.
  • Use a compressed Trie (Radix Tree) to reduce space for long strings with shared prefixes.

FAQ

What is the main idea behind implementing a Trie (Prefix Tree)?

Use a tree structure where each node represents a character, storing children in a hash map and marking nodes that complete words.

How does the startsWith function differ from search in a Trie?

startsWith only checks that a path exists for the given prefix, while search also verifies the end-of-word flag to ensure a full word match.

Can I use arrays instead of hash maps for children in a Trie?

Yes, but arrays may waste space for sparse character sets; hash maps are more memory efficient for lowercase English letters.

What is the time complexity of insert, search, and startsWith?

All operations are O(L), where L is the length of the word or prefix, because each character requires a single lookup in the hash map.

How does this problem relate to the Hash Table plus String pattern?

Each Trie node uses a hash map (hash table) to store children characters, combining tree traversal with string processing for efficient queries.

terminal

Solution

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Trie:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False

    def insert(self, word: str) -> None:
        node = self
        for c in word:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                node.children[idx] = Trie()
            node = node.children[idx]
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self._search_prefix(word)
        return node is not None and node.is_end

    def startsWith(self, prefix: str) -> bool:
        node = self._search_prefix(prefix)
        return node is not None

    def _search_prefix(self, prefix: str):
        node = self
        for c in prefix:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                return None
            node = node.children[idx]
        return node


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Trie:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False

    def insert(self, word: str) -> None:
        node = self
        for c in word:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                node.children[idx] = Trie()
            node = node.children[idx]
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self._search_prefix(word)
        return node is not None and node.is_end

    def startsWith(self, prefix: str) -> bool:
        node = self._search_prefix(prefix)
        return node is not None

    def _search_prefix(self, prefix: str):
        node = self
        for c in prefix:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                return None
            node = node.children[idx]
        return node


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

Solution 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Trie:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False

    def insert(self, word: str) -> None:
        node = self
        for c in word:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                node.children[idx] = Trie()
            node = node.children[idx]
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self._search_prefix(word)
        return node is not None and node.is_end

    def startsWith(self, prefix: str) -> bool:
        node = self._search_prefix(prefix)
        return node is not None

    def _search_prefix(self, prefix: str):
        node = self
        for c in prefix:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                return None
            node = node.children[idx]
        return node


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

Continue Practicing

#676 implement magic dictionary#677 map sum pairs#745 prefix and suffix search
category

Continue Topic

hash table

Practice more edge cases under the same topic.

arrow_forwardauto_awesome

Continue Pattern

Hash Table plus String

Expand the same solving frame across more problems.

arrow_forwardsignal_cellular_alt

Same Difficulty Track

Medium

Stay on this level to stabilize interview delivery.

arrow_forward
Implement Trie (Prefix Tree) Solution: Hash Table plus String | LeetCode #208 Medium