Longest Word in Dictionary Using Trie in DSA Go

Mental Model

Build a tree where each path is a word, then find the longest word where every prefix is also a word.

Analogy: Imagine a family tree where each generation must be complete before moving to the next; the longest name is the deepest complete branch.

root
 ↓
 t -> r -> i -> e
 ↑
 start

Dry Run Walkthrough

Input: words: ["a", "ap", "app", "appl", "apple", "apply"]

Goal: Find the longest word where all prefixes are also words in the list

Step 1: Insert 'a' into trie

root -> a[isWord=true]

Why: Start building trie with first word

Step 2: Insert 'ap' into trie

root -> a[isWord=true] -> p[isWord=true]

Why: Add second word, marking prefix 'ap' as word

Step 3: Insert 'app' into trie

root -> a[isWord=true] -> p[isWord=true] -> p[isWord=true]

Why: Add third word, all prefixes so far are words

Step 4: Insert 'appl' into trie

root -> a[isWord=true] -> p[isWord=true] -> p[isWord=true] -> l[isWord=true]

Why: Add fourth word, prefix 'appl' is word

Step 5: Insert 'apple' into trie

root -> a[isWord=true] -> p[isWord=true] -> p[isWord=true] -> l[isWord=true] -> e[isWord=true]

Why: Add fifth word, all prefixes valid

Step 6: Insert 'apply' into trie

root -> a[isWord=true] -> p[isWord=true] -> p[isWord=true] -> l[isWord=true] -> y[isWord=true]

Why: Add sixth word, all prefixes valid

Step 7: Search longest word with all prefixes as words

Check words: 'a', 'ap', 'app', 'appl', 'apple', 'apply'

Why: Find longest valid word

Step 8: Choose 'apple' as longest valid word (lex smaller than 'apply')

Result: 'apple'

Why: Both 'apple' and 'apply' valid, choose lex smaller

Result:

apple

Annotated Code

DSA Go

package main

import (
	"fmt"
)

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

func NewTrieNode() *TrieNode {
	return &TrieNode{children: make(map[rune]*TrieNode)}
}

type Trie struct {
	root *TrieNode
}

func NewTrie() *Trie {
	return &Trie{root: NewTrieNode()}
}

func (t *Trie) Insert(word string) {
	curr := t.root
	for _, ch := range word {
		if curr.children[ch] == nil {
			curr.children[ch] = NewTrieNode()
		}
		curr = curr.children[ch]
	}
	curr.isWord = true
}

func (t *Trie) LongestWord() string {
	var result string
	var dfs func(node *TrieNode, path []rune)
	dfs = func(node *TrieNode, path []rune) {
		if node != t.root && !node.isWord {
			return
		}
		if len(path) > len(result) || (len(path) == len(result) && string(path) < result) {
			result = string(path)
		}
		for ch := 'a'; ch <= 'z'; ch++ {
			if node.children[ch] != nil {
				dfs(node.children[ch], append(path, ch))
			}
		}
	}
	dfs(t.root, []rune{})
	return result
}

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

for _, ch := range word { if curr.children[ch] == nil { curr.children[ch] = NewTrieNode() } curr = curr.children[ch] }

Insert each character, creating nodes if missing, advancing current pointer

curr.isWord = true

Mark end of inserted word as valid word

if node != t.root && !node.isWord { return }

Stop DFS if current node is not a word (prefix missing)

if len(path) > len(result) || (len(path) == len(result) && string(path) < result) { result = string(path) }

Update result if current path is longer or lex smaller when equal length

for ch := 'a'; ch <= 'z'; ch++ { if node.children[ch] != nil { dfs(node.children[ch], append(path, ch)) } }

DFS children in alphabetical order to ensure lex order

Output

apple

Complexity Analysis

Time: O(N * L) because we insert N words each of length L and DFS visits nodes once

Space: O(N * L) for trie nodes storing all characters of all words

vs Alternative: Compared to sorting and checking prefixes in array (O(N log N * L)), trie offers efficient prefix checks

Edge Cases

Empty word list

Returns empty string as no words exist

DSA Go

if node != t.root && !node.isWord { return }

Words with no valid prefixes except single letters

Returns shortest valid word with all prefixes present

DSA Go

if node != t.root && !node.isWord { return }

Multiple longest words with same length

Returns lexicographically smallest word

DSA Go

if len(path) > len(result) || (len(path) == len(result) && string(path) < result) { result = string(path) }

When to Use This Pattern

When asked to find the longest word with all prefixes present, use a trie to efficiently check prefixes and find the answer by DFS.

Common Mistakes

Mistake: Not checking if all prefixes are words before updating result
Fix: Add condition to stop DFS if current node is not marked as word

Mistake: Not exploring children in alphabetical order causing wrong lexicographical result
Fix: Traverse children from 'a' to 'z' to ensure lex order

Summary

Build a trie from words and find the longest word where every prefix is also a word.

Use when you need to find words with all prefixes present efficiently.

The key is to stop exploring paths where prefixes are missing and to explore children in alphabetical order.

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