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.