We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Implement Trie (Prefix Tree)

Difficulty: Medium

Problem Description

Implement a trie (prefix tree) data structure that supports the following operations: inserting a word, searching for a word, and checking if any word in the trie starts with a given prefix.

Key Insights

  • A trie is a tree-like data structure that stores strings efficiently.
  • Each node in the trie represents a character of a string.
  • The insertion of a string is done character by character.
  • Searching for a word or prefix involves traversing the trie based on the characters of the input.

Space and Time Complexity

Time Complexity:

  • Insert: O(m), where m is the length of the word being inserted.
  • Search: O(m), where m is the length of the word being searched.
  • StartsWith: O(m), where m is the length of the prefix being checked.

Space Complexity: O(n * m), where n is the number of words stored in the trie and m is the maximum length of the words.

Solution

The solution uses a trie data structure, which consists of nodes where each node contains a map of children nodes representing subsequent characters. The root node represents an empty prefix. The insert method adds words to the trie by creating nodes for each character if they do not already exist. The search method checks for the existence of a word by traversing the trie according to the characters of the word. The startsWith method checks for the existence of any word with the given prefix by following the same traversal logic.

Code Solutions

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True
← Back to All Questions