Word Search in Trie in DSA Go - Build from Scratch

Word Search in Trie

📖 Scenario: You are building a simple word search tool that can quickly check if a word exists in a dictionary. To do this efficiently, you will use a Trie data structure, which stores words in a tree-like form.Imagine a phone's autocomplete feature that suggests words as you type. The Trie helps find words fast by sharing common prefixes.

🎯 Goal: Build a Trie to store a list of words, then search for a specific word in the Trie to check if it exists.

📋 What You'll Learn

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

Insert given words into the Trie

Search for a given word in the Trie

Print whether the word exists or not

💡 Why This Matters

🌍 Real World

Tries are used in autocomplete systems, spell checkers, and IP routing to quickly find words or prefixes.

💼 Career

Understanding Tries helps in roles involving search engines, text processing, and efficient data retrieval.

1

Create Trie Node Structure

Create a struct called TrieNode with a field children which is a map from rune to *TrieNode, and a boolean field isEndOfWord.

DSA Go

// Your code here

Hint

Use map[rune]*TrieNode for children to store links to next letters.

2

Initialize Trie Root and Insert Words

Create a variable root of type *TrieNode initialized with an empty children map. Then write a function insertWord that takes root *TrieNode and word string and inserts the word into the Trie by creating nodes as needed.

DSA Go

root := &TrieNode{children: make(map[rune]*TrieNode)}

// Your code here

Hint

Initialize root with an empty map. Loop over each character in word. Create new nodes if missing.

3

Search for a Word in the Trie

Write a function searchWord that takes root *TrieNode and word string and returns bool. It should return true if the word exists in the Trie, otherwise false. Use a loop to traverse the Trie nodes for each character.

DSA Go

func searchWord(root *TrieNode, word string) bool {
    // Your code here
}

Hint

Traverse the Trie for each character. If a character node is missing, return false. After the loop, check if isEndOfWord is true.

4

Print Search Result

In main, call searchWord with root and the word "golang". Print "Found" if it returns true, otherwise print "Not Found".

DSA Go

    // Your code here

Hint

Use if searchWord(root, "golang") then println("Found") else println("Not Found").