Longest Word in Dictionary Using Trie in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Longest Word Search in Trie

What is the output of the following Go code that builds a Trie from a list of words and finds the longest word where all prefixes are also words in the list?

DSA Go

package main

import "fmt"

// TrieNode represents a node in the Trie
type TrieNode struct {
    children map[rune]*TrieNode
    isWord   bool
}

// Trie structure
type Trie struct {
    root *TrieNode
}

// Insert inserts a word into the Trie
func (t *Trie) Insert(word string) {
    node := t.root
    for _, ch := range word {
        if node.children[ch] == nil {
            node.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
        }
        node = node.children[ch]
    }
    node.isWord = true
}

// LongestWord finds the longest word with all prefixes present
func (t *Trie) LongestWord() string {
    var result string
    var dfs func(node *TrieNode, path []rune)
    dfs = func(node *TrieNode, path []rune) {
        if len(path) > len(result) || (len(path) == len(result) && string(path) < result) {
            result = string(path)
        }
        for ch := range node.children {
            child := node.children[ch]
            if child.isWord {
                dfs(child, append(path, ch))
            }
        }
    }
    dfs(t.root, []rune{})
    return result
}

func main() {
    words := []string{"a", "app", "ap", "apply", "apple", "appl"}
    trie := &Trie{root: &TrieNode{children: make(map[rune]*TrieNode)}}
    for _, w := range words {
        trie.Insert(w)
    }
    fmt.Println(trie.LongestWord())
}

A "apply"

B "app"

C "apple"

D "appl"

💡 Hint

Check which words have all their prefixes also present in the list.

The code builds a Trie and searches for the longest word where every prefix is also a word in the list. Among the words, "apple" and "apply" are longest. Both "apple" and "apply" have all prefixes present, but lex order chooses "apple".

🧠 Conceptual

intermediate

Understanding Trie Node Structure

Which of the following best describes the purpose of the 'isWord' boolean in a Trie node when finding the longest word in a dictionary?

A It indicates if the node has any children nodes.

B It counts how many words pass through this node.

C It stores the character value of the node.

D It marks whether the node represents the end of a valid word in the dictionary.

💡 Hint

Think about how to know if a prefix is a complete word.

The 'isWord' boolean marks if the path to this node forms a complete word in the dictionary. This is crucial to check if all prefixes exist when searching for the longest word.

🔧 Debug

advanced

Identify the Bug in Trie Longest Word Search

What error will occur if the DFS function in the Trie LongestWord method does not check if child.isWord before recursing?

DSA Go

func (t *Trie) LongestWord() string {
    var result string
    var dfs func(node *TrieNode, path []rune)
    dfs = func(node *TrieNode, path []rune) {
        if len(path) > len(result) || (len(path) == len(result) && string(path) < result) {
            result = string(path)
        }
        for ch := range node.children {
            child := node.children[ch]
            // Missing check: if child.isWord
            dfs(child, append(path, ch))
        }
    }
    dfs(t.root, []rune{})
    return result
}

A The DFS will never terminate, causing infinite recursion.

B The function will include incomplete prefixes, resulting in incorrect longest word output.

C The code will produce a compilation error due to missing isWord check.

D The code will cause a runtime panic due to nil pointer dereference.

💡 Hint

Consider what happens if prefixes are not validated as words.

Without checking if child.isWord, the DFS explores nodes that do not represent complete words, so the result may include words whose prefixes are not valid words, violating the problem's condition.

🚀 Application

advanced

Longest Word Result After Insertions

Given the words inserted into the Trie: ["w", "wo", "wor", "worl", "world", "word", "war"], what will be the longest word returned by the LongestWord method?

A "world"

B "word"

C "war"

D "worl"

💡 Hint

Check which words have all prefixes present and are longest.

"world" has all prefixes "w", "wo", "wor", "worl" present as words. "word" also has prefixes but is shorter. "war" is shorter and "worl" is prefix but not longest.

🧠 Conceptual

expert

Lexicographical Order in Longest Word Selection

Why does the LongestWord method compare strings lexicographically when lengths are equal during DFS?

A To ensure the lexicographically smallest word is chosen among words of the same length.

B To speed up the DFS traversal by pruning branches early.

C To avoid visiting nodes that do not form valid words.

D To count the total number of words stored in the Trie.

💡 Hint

Think about tie-breaking when multiple words have the same length.

When multiple words have the same length, the problem requires choosing the lexicographically smallest one. Comparing strings lex order ensures this.