MediumBlind75StringTrieDesign

Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.

Examples

Input
trie.insert('apple'); trie.search('apple'); trie.startsWith('app')
Output
true, true

Insert 'apple', search finds it, startsWith('app') is true.

Input
trie.search('app')
Output
false

'app' is not a complete word.

Constraints

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

Approaches

Use arrays to represent children for each node.

CodeT: O(m) per operation | S: O(m)
class TrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):
        node = self.root
        for char in word:
            idx = ord(char) - ord('a')
            if not node.children[idx]:
                node.children[idx] = TrieNode()
            node = node.children[idx]
        node.is_end = True
    def search(self, word):
        node = self.root
        for char in word:
            idx = ord(char) - ord('a')
            if not node.children[idx]:
                return False
            node = node.children[idx]
        return node.is_end
    def startsWith(self, prefix):
        node = self.root
        for char in prefix:
            idx = ord(char) - ord('a')
            if not node.children[idx]:
                return False
            node = node.children[idx]
        return True

Use dictionaries for flexible character mapping.

CodeT: O(m) per operation | S: O(m)
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end
    def startsWith(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

Same hash map approach with cleaner code.

Diagram

insert('apple'): root->a->p->p->l->e(is_end) search('apple'): traverse to e, is_end=True -> True startsWith('app'): traverse to p -> True search('app'): traverse to p, is_end=False -> False
CodeT: O(m) per operation | S: O(m)
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):
        node = self.root
        for c in word:
            node = node.children.setdefault(c, TrieNode())
        node.is_end = True
    def search(self, word):
        node = self._find(word)
        return node is not None and node.is_end
    def startsWith(self, prefix):
        return self._find(prefix) is not None
    def _find(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node.children:
                return None
            node = node.children[c]
        return node

Complexity Comparison

Array-Based Trie
T: O(m) per operationS: O(m)

Use arrays to represent children for each node.

Hash Map-Based Trie
T: O(m) per operationS: O(m)

Use dictionaries for flexible character mapping.

Optimized Trie
T: O(m) per operationS: O(m)

Same hash map approach with cleaner code.

Common Mistakes

Not marking the end of a complete word

Using a fixed-size array when the character set is unknown

Not handling the case where a prefix is a complete word

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems