Prefix matching with tries in Data Structures Theory - Mini Project: Build & Apply

Prefix Matching with Tries

📖 Scenario: Imagine you are building a simple phone contact search system. When a user types the first few letters of a name, the system should quickly find all contacts that start with those letters.

🎯 Goal: You will build a basic trie data structure step-by-step to store contact names and then find all names that start with a given prefix.

📋 What You'll Learn

Create a trie node structure to hold children and end-of-word marker

Add a configuration variable to hold the root of the trie

Insert a list of contact names into the trie

Implement a prefix search function to find all contacts starting with a given prefix

💡 Why This Matters

🌍 Real World

Tries are used in search engines, autocomplete features, and contact lists to quickly find words or names starting with certain letters.

💼 Career

Understanding tries helps in software development roles involving search optimization, text processing, and building efficient data structures.

1

Create the Trie Node Structure

Create a class called TrieNode with an __init__ method that initializes two attributes: children as an empty dictionary and is_end_of_word as False.

Data Structures Theory

# Your code here

Need a hint?

Think of each node as a letter holder with links to next letters and a flag to mark if a word ends here.

2

Create the Trie Root Node

Create a variable called root and assign it a new instance of TrieNode().

Data Structures Theory

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

# Your code here

Need a hint?

The root node is the starting point of the trie. It does not hold a letter itself.

3

Insert Contact Names into the Trie

Create a function called insert that takes a word string and inserts it into the trie starting from the root. Use a for loop with variable char to iterate over each character in word. For each character, if it is not in current.children, add a new TrieNode(). Move current to the child node for that character. After the loop, set current.is_end_of_word to True. Then, insert the names "Anna", "Anne", and "Annie" by calling insert for each.

Data Structures Theory

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

root = TrieNode()

# Your code here

Need a hint?

Each character creates or moves to a child node. Mark the end of the word after inserting all characters.

4

Implement Prefix Search Function

Create a function called search_prefix that takes a prefix string and returns a list of all words in the trie that start with that prefix. First, use a for loop with variable char to traverse the trie from root following the prefix characters. If a character is missing, return an empty list. Then, define a helper function dfs that takes a node and path string and recursively collects all words starting from that node. Use dfs to collect and return all matching words with the prefix.

Data Structures Theory

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

root = TrieNode()

def insert(word):
    current = root
    for char in word:
        if char not in current.children:
            current.children[char] = TrieNode()
        current = current.children[char]
    current.is_end_of_word = True

insert("Anna")
insert("Anne")
insert("Annie")

# Your code here

Need a hint?

First find the node matching the prefix, then explore all words below it using depth-first search.