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

Longest Word in Dictionary Using Trie

📖 Scenario: Imagine you are building a word game helper tool. You want to find the longest word from a list of words where every prefix of the word is also a valid word in the list. This helps players find the best possible word to play.

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

📋 What You'll Learn

Create a Trie node structure with children and end-of-word marker

Insert words into the Trie

Traverse the Trie to find the longest valid word where all prefixes exist

Print the longest word found

💡 Why This Matters

🌍 Real World

Tries are used in autocomplete systems, spell checkers, and word games to quickly find words and prefixes.

💼 Career

Understanding Tries and prefix-based searches is useful for software engineers working on search engines, text processing, and game development.

1

Create the initial list of words

Create a slice of strings called words with these exact values: "a", "app", "ap", "apply", "apple"

DSA Go

# Create the slice words with the given words
# Your code here

Hint

Use var words = []string{...} to create the list.

2

Define the Trie node structure and root

Define a struct called TrieNode with a field children as an array of 26 pointers to TrieNode and a boolean field isEnd. Then create a variable root as a pointer to a new TrieNode.

DSA Go

package main

var words = []string{"a", "app", "ap", "apply", "apple"}

type TrieNode struct {
    children [26]*TrieNode
    isEnd    bool
}

var root = &TrieNode{}

func main() {
    // Your code here
}

Hint

Use an array of 26 pointers for children to represent letters 'a' to 'z'. Initialize root as a pointer to an empty TrieNode.

3

Insert words into the Trie

Write a function insertWord that takes a string word and inserts it into the Trie starting from root. Then, in main, use a for loop with variable w to insert each word from words by calling insertWord(w).

DSA Go

package main

var words = []string{"a", "app", "ap", "apply", "apple"}

type TrieNode struct {
    children [26]*TrieNode
    isEnd    bool
}

var root = &TrieNode{}

func insertWord(word string) {
    // Your code here
}

func main() {
    for _, w := range words {
        insertWord(w)
    }
}

Hint

Traverse each character, create nodes if missing, and mark the end of the word.

4

Find and print the longest valid word

Write a function longestWord that returns the longest word in the Trie such that all prefixes are marked as isEnd. Use a recursive helper function dfs starting from root with an empty string. In main, call longestWord() and print the result using fmt.Println.

DSA Go

package main

import "fmt"

var words = []string{"a", "app", "ap", "apply", "apple"}

type TrieNode struct {
    children [26]*TrieNode
    isEnd    bool
}

var root = &TrieNode{}

func insertWord(word string) {
    node := root
    for _, ch := range word {
        index := ch - 'a'
        if node.children[index] == nil {
            node.children[index] = &TrieNode{}
        }
        node = node.children[index]
    }
    node.isEnd = true
}

func longestWord() string {
    // Your code here
    return ""
}

func main() {
    for _, w := range words {
        insertWord(w)
    }
    // Print the longest word
    // Your code here
}

Hint

Use depth-first search to explore children only if isEnd is true. Keep track of 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 reverse the words quickly

B. To sort words alphabetically

C. To count the total number of words

D. To efficiently store and search words by their prefixes

Solution

1. Step 1: Understand Trie usage

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

2. Step 2: Connect Trie to longest word search

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

3. Final Answer:

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

4. Quick Check:

   Trie = prefix search [OK]

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

Common Mistakes:

• Confusing Trie with sorting algorithms
• Thinking Trie reverses words
• Assuming Trie counts words only

2. Which of the following Go code snippets correctly initializes a Trie node struct for storing children nodes?

easy

A. type TrieNode struct { children map[int]string; isWord string }

B. type TrieNode struct { children []int; isWord int }

C. type TrieNode struct { children map[rune]*TrieNode; isWord bool }

D. type TrieNode struct { children []string; isWord bool }

Solution

1. Step 1: Identify correct children type

   Children should map characters (rune) to TrieNode pointers for branching.

2. Step 2: Check isWord type

   isWord is a boolean indicating if node ends a valid word.

3. Final Answer:

   type TrieNode struct { children map[rune]*TrieNode; isWord bool } -> Option C

4. Quick Check:

   Children map[rune]*TrieNode and bool isWord [OK]

Hint: Children map uses rune keys and TrieNode pointers [OK]

Common Mistakes:

• Using slices instead of maps for children
• Wrong data types for children or isWord
• Using int or string instead of rune keys

3. Given the following Go code snippet that inserts words into a Trie and finds the longest word, what will be printed?

words := []string{"a", "app", "apple", "apply", "ap"}
trie := NewTrie()
for _, w := range words {
    trie.Insert(w)
}
result := trie.LongestWord()
fmt.Println(result)

medium

A. "app"

B. "apply"

C. "a"

D. "apple"

Solution

1. Step 1: Insert words into Trie

   All words "a", "ap", "app", "apple", "apply" are inserted.

2. Step 2: Find longest word built from prefixes

   "app" has all prefixes "a", "ap", "app" present as words. "apple" and "apply" lack "appl" prefix.

3. Final Answer:

   "app" -> Option A

4. Quick Check:

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

Hint: Longest word with all prefixes present wins, lex order breaks ties [OK]

Common Mistakes:

• Choosing "apple" or "apply" ignoring missing "appl"
• Picking lexicographically later word
• Not inserting all words before search

4. In the following Go code for inserting words into a Trie, what is the bug that prevents correct longest word detection?

func (t *Trie) Insert(word string) {
    node := t.root
    for _, ch := range word {
        if node.children[ch] == nil {
            node.children[ch] = &TrieNode{}
        }
        node = node.children[ch]
    }
    node.isWord = false
}

medium

A. isWord should be set to true, not false

B. children map is not initialized

C. Loop variable ch should be int, not rune

D. Function should return a value

Solution

1. Step 1: Check isWord assignment

   isWord marks end of a valid word and must be true, not false.

2. Step 2: Understand impact on longest word search

   Setting isWord false means no word end is recognized, breaking longest word logic.

3. Final Answer:

   isWord should be set to true, not false -> Option A

4. Quick Check:

   isWord = true marks word end [OK]

Hint: Set isWord true at word end to mark valid words [OK]

Common Mistakes:

• Setting isWord false instead of true
• Not initializing children map before use
• Ignoring rune type for characters

5. You have a list of words: ["w", "wo", "wor", "worl", "world", "banana", "ban", "bana", "banan"]. Using a Trie, which word will be the longest word in the dictionary where every prefix is also a word? Assume ties are broken by lexicographical order.

hard

A. "worl"

B. "world"

C. "banana"

D. "banan"

Solution

1. Step 1: Check prefixes for each candidate

   "world" has prefixes "w", "wo", "wor", "worl" all present.

2. Step 2: Check "banana" and its prefixes

   "banana" lacks prefixes like "b", "ba", so it fails.

3. Step 3: Compare longest valid words

   "world" (length 5) is longest with all prefixes present; "banana" (6) invalid, "banan" also invalid.

4. Final Answer:

   "world" -> Option B

5. Quick Check:

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

Hint: Check all prefixes exist; longest with lex order wins [OK]

Common Mistakes:

• Ignoring missing prefixes for banana
• Choosing shorter words
• Not applying lexicographical tie-break