Trie Data Structure

1. Understand Trie

The Trie data structure is a tree-like data structure used for storing a dynamic set of strings (also called prefix tree).

There are 2 widely used method of Trie: Insert, Search.

2. Implementation

Let’s implement a Trie class with Python:

Define a TrieNode:

class TrieNode:
  def __init__(self):
    self.children: dict[str, TrieNode] = {}

Define a Trie with 2 methods:

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

  def insert(self, word: str) -> None:
    node: TrieNode = self.root
    for c in word:
      node = node.children.setdefault(c, TrieNode())
    node.isWord = True

  def search(self, word: str) -> int:
    prefixLength = 0
    node = self.root
    for c in word:
      if c not in node.children:
        break
      node = node.children[c]
      prefixLength += 1
    return prefixLength

The search method can be modified for each usage purpose.

Refs:

https://www.geeksforgeeks.org/trie-insert-and-search/