Longest Word in Dictionary Using Trie in DSA Python - Build from Scratch

Longest Word in Dictionary Using Trie

📖 Scenario: You are building a word game helper tool. You want to find the longest word in a dictionary where every prefix of the word is also a valid word in the dictionary. This helps players find the best words to score points.

🎯 Goal: Build a program that uses a Trie data structure to find the longest word in a given list of words such that all prefixes of the word are also present in the list.

📋 What You'll Learn

Create a TrieNode class with children and end-of-word marker

Insert all words from the given list into the Trie

Traverse the Trie to find the longest word with all prefixes present

Print the longest valid word found

💡 Why This Matters

🌍 Real World

Word games and auto-complete systems use tries to quickly find valid words and prefixes.

💼 Career

Understanding tries and prefix searches is useful for software roles involving search engines, text processing, and game development.

1

Create the TrieNode class and insert words

Create a class called TrieNode with an attribute children as a dictionary and is_end as False. Then create a class called Trie with a method insert that inserts a word into the Trie. Finally, create a list called words with these exact words: "w", "wo", "wor", "worl", "world".

DSA Python

# Define TrieNode and Trie classes
# Create list words with exact entries
# Your code here

Hint

Start by defining the TrieNode class with children and is_end attributes. Then define the Trie class with an insert method. Finally, create the list words with the given words.

2

Insert all words into the Trie

Create an instance of Trie called trie. Use a for loop with variable word to insert each word from the words list into the trie using the insert method.

DSA Python

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

words = ["w", "wo", "wor", "worl", "world"]

# Create trie instance and insert words
# Your code here

Hint

Create a Trie object called trie. Then loop over each word in words and insert it into the trie.

3

Find the longest word with all prefixes present

Define a function called longest_word that takes the trie root node as input. Use a depth-first search (DFS) approach with a helper function dfs that takes a node and current path string. Only continue DFS if node.is_end is True or if node is the root. Update a variable longest to store the longest valid word found. Call dfs starting from the root with an empty string and return longest.

DSA Python

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

words = ["w", "wo", "wor", "worl", "world"]

trie = Trie()
for word in words:
    trie.insert(word)

# Define longest_word function using DFS
# Your code here

Hint

Use a recursive function longest_word to explore children only if current node marks end of a word or is root. Keep track of the longest valid word found in a global variable.

4

Print the longest valid word found

Write a print statement to display the value of the variable longest which holds the longest word found with all prefixes present.

DSA Python

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

words = ["w", "wo", "wor", "worl", "world"]

trie = Trie()
for word in words:
    trie.insert(word)

longest = ""
def longest_word(node, path):
    global longest
    if node != trie.root and not node.is_end:
        return
    if len(path) > len(longest) or (len(path) == len(longest) and path < longest):
        longest = path
    for char in sorted(node.children.keys()):
        longest_word(node.children[char], path + char)

longest_word(trie.root, "")

# Print the longest word
# Your code here

Hint

Simply print the variable longest to show the longest word found.

Practice

1. What is the main purpose of using a Trie data structure when finding the longest word in a dictionary?

easy

A. To efficiently store and search words by their prefixes

B. To sort words alphabetically

C. To count the total number of words

D. To reverse the words in the dictionary

Solution

1. Step 1: Understand Trie usage

   A Trie stores words by breaking them into characters and linking nodes for prefixes.

2. Step 2: Relate Trie to longest word search

   This structure allows quick prefix checks, which helps find the longest word built from other words.

3. Final Answer:

   To efficiently store and search words by their prefixes -> Option A

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie is best for prefix-based word searches [OK]

Common Mistakes:

• Thinking Trie sorts words alphabetically
• Confusing Trie with simple lists
• Assuming Trie counts words only

2. Which of the following is the correct way to insert a word into a Trie node in Python?

easy

A. node.children[char] = TrieNode() if char not in node.children else node.children[char]

B. node.children.add(char)

C. node.children.append(char)

D. node.children[char] = char

Solution

1. Step 1: Understand Trie children structure

   Trie children are stored in a dictionary mapping characters to TrieNode objects.

2. Step 2: Correct insertion method

   We check if character exists; if not, create new TrieNode and assign it to children dictionary.

3. Final Answer:

   node.children[char] = TrieNode() if char not in node.children else node.children[char] -> Option A

4. Quick Check:

   Insert uses dictionary with TrieNode [OK]

Hint: Use dictionary keys for children, not list or set [OK]

Common Mistakes:

• Using add() or append() on dictionary
• Assigning character instead of TrieNode
• Not checking if child exists before insertion

3. Given the words: ["a", "app", "apple", "apply", "ap"], what is the longest word that can be built one character at a time using the Trie method?

medium

A. "apply"

B. "app"

C. "apple"

D. "ap"

Solution

1. Step 1: Check each word's prefixes

   Words must have all prefixes present: "a", "ap", "app" are present; "apple" and "apply" require "appl" which is missing.

2. Step 2: Identify longest valid word

   "app" is the longest word where all prefixes exist in the list.

3. Final Answer:

   "app" -> Option B

4. Quick Check:

   Longest word with all prefixes = "app" [OK]

Hint: Check all prefixes exist before choosing longest word [OK]

Common Mistakes:

• Assuming "apple" or "apply" are valid without "appl"
• Ignoring prefix requirement
• Choosing shortest word instead

4. What is the error in this Trie insertion code snippet for building the longest word?

for word in words:
    node = root
    for char in word:
        if char not in node.children:
            node.children[char] = TrieNode
        node = node.children[char]
    node.is_word = True

medium

A. The root node should be reset after each character

B. The loop should iterate over characters in reverse

C. node.is_word should be set before the inner loop

D. TrieNode should be called with parentheses to create an instance

Solution

1. Step 1: Identify object creation mistake

   TrieNode is a class; to create an object, parentheses () are needed.

2. Step 2: Understand impact of missing parentheses

   Without (), node.children[char] stores the class itself, not an instance, causing errors on further access.

3. Final Answer:

   TrieNode should be called with parentheses to create an instance -> Option D

4. Quick Check:

   Instantiate TrieNode with () [OK]

Hint: Always use () to create class instances in Python [OK]

Common Mistakes:

• Forgetting parentheses when creating objects
• Setting flags in wrong loop place
• Resetting root incorrectly inside loops

5. You have a list of words: ["w", "wo", "wor", "worl", "world", "banana", "ban", "bana", "banan"]. Using a Trie, which word will be returned as the longest word built one character at a time from other words in the list?

hard

A. "worl"

B. "banana"

C. "world"

D. "banan"

Solution

1. Step 1: Verify prefix chains for each candidate

   "world" prefixes: "w", "wo", "wor", "worl", "world" all exist; "banana" and "banan" missing prefixes like "b", "ba"; "worl" is shorter than "world".

2. Step 2: Choose longest word with all prefixes present

   "world" is longest with all prefixes present in the list.

3. Final Answer:

   "world" -> Option C

4. Quick Check:

   Longest word with full prefix chain = "world" [OK]

Hint: Check full prefix chain exists before longest word [OK]

Common Mistakes:

• Choosing "banana" without full prefix chain
• Ignoring prefix requirement for "banan"
• Picking shorter word "worl" over "world"