Longest Word in Dictionary Using Trie in DSA C# - Build from Scratch

Longest Word in Dictionary Using Trie

📖 Scenario: Imagine you have a list of words from a dictionary. You want to find the longest word that can be built one character at a time by other words in the list. For example, if the word "apple" is in the list, then "a", "ap", "app", and "appl" must also be in the list for "apple" to count.

🎯 Goal: You will build a Trie data structure to store the words. Then, you will find the longest word that can be built character by character from other words in the dictionary.

📋 What You'll Learn

Create a TrieNode class with children and a flag for word end

Insert words into the Trie

Use a helper variable to track the longest word found

Traverse the Trie to find the longest valid word

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 string search algorithms is important for software engineers working on search engines, text processing, and data compression.

1

Create TrieNode class and insert words

Create a class called TrieNode with a Dictionary<char, TrieNode> called children and a bool called isWord. Then create a class called Trie with a TrieNode called root. Finally, create a method Insert(string word) in Trie that inserts the exact words "a", "ap", "app", "appl", and "apple" into the Trie.

DSA C#

// Your code here to create TrieNode, Trie classes and insert words

Hint

Use a dictionary to store children nodes. Mark isWord true when a word ends.

2

Add a variable to track the longest word

Add a string variable called longestWord in the Program class and set it to an empty string "".

DSA C#

using System;
using System.Collections.Generic;

class TrieNode
{
    public Dictionary children = new Dictionary();
    public bool isWord = false;
}

class Trie
{
    public TrieNode root = new TrieNode();

    public void Insert(string word)
    {
        TrieNode node = root;
        foreach (char c in word)
        {
            if (!node.children.ContainsKey(c))
            {
                node.children[c] = new TrieNode();
            }
            node = node.children[c];
        }
        node.isWord = true;
    }
}

class Program
{
    static void Main()
    {
        Trie trie = new Trie();
        trie.Insert("a");
        trie.Insert("ap");
        trie.Insert("app");
        trie.Insert("appl");
        trie.Insert("apple");

        string longestWord = ""; // Your code here

Hint

Use a string variable to keep track of the longest word found so far.

3

Traverse the Trie to find the longest word

Add a method FindLongestWord() in the Trie class that uses a DFS helper method to find the longest word where every prefix is a word. Use a string parameter currentWord to build words during traversal. Update the longestWord variable in Program if a longer valid word is found.

DSA C#

using System;
using System.Collections.Generic;

class TrieNode
{
    public Dictionary children = new Dictionary();
    public bool isWord = false;
}

class Trie
{
    public TrieNode root = new TrieNode();

    public void Insert(string word)
    {
        TrieNode node = root;
        foreach (char c in word)
        {
            if (!node.children.ContainsKey(c))
            {
                node.children[c] = new TrieNode();
            }
            node = node.children[c];
        }
        node.isWord = true;
    }

    // Add FindLongestWord method and DFS helper here
}

class Program
{
    static void Main()
    {
        Trie trie = new Trie();
        trie.Insert("a");
        trie.Insert("ap");
        trie.Insert("app");
        trie.Insert("appl");
        trie.Insert("apple");

        string longestWord = "";

        // Call FindLongestWord and update longestWord
    }
}

Hint

Use DFS to explore all paths. Only continue if current node marks a word. Update longestWord if currentWord is longer or lexicographically smaller when equal length.

4

Print the longest word found

Add a Console.WriteLine(longestWord); statement in the Main method to print the longest word found by FindLongestWord().

DSA C#

using System;
using System.Collections.Generic;

class TrieNode
{
    public Dictionary children = new Dictionary();
    public bool isWord = false;
}

class Trie
{
    public TrieNode root = new TrieNode();

    public void Insert(string word)
    {
        TrieNode node = root;
        foreach (char c in word)
        {
            if (!node.children.ContainsKey(c))
            {
                node.children[c] = new TrieNode();
            }
            node = node.children[c];
        }
        node.isWord = true;
    }

    public string FindLongestWord()
    {
        string longestWord = "";
        DFS(root, "", ref longestWord);
        return longestWord;
    }

    private void DFS(TrieNode node, string currentWord, ref string longestWord)
    {
        if (node != root && !node.isWord)
            return;

        if (currentWord.Length > longestWord.Length ||
            (currentWord.Length == longestWord.Length && string.Compare(currentWord, longestWord) < 0))
        {
            longestWord = currentWord;
        }

        foreach (var child in node.children)
        {
            DFS(child.Value, currentWord + child.Key, ref longestWord);
        }
    }
}

class Program
{
    static void Main()
    {
        Trie trie = new Trie();
        trie.Insert("a");
        trie.Insert("ap");
        trie.Insert("app");
        trie.Insert("appl");
        trie.Insert("apple");

        string longestWord = trie.FindLongestWord();

        // Print the longest word
    }
}

Hint

Use Console.WriteLine(longestWord); to show the result.

Practice

1. What is the main purpose of using a Trie data structure when finding the longest word in a dictionary?

easy

A. To sort words alphabetically

B. To efficiently store and search words by their prefixes

C. To count the total number of words

D. To reverse the words in the dictionary

Solution

1. Step 1: Understand Trie structure

   A Trie stores words by sharing common prefixes, making prefix searches fast.

2. Step 2: Relate to longest word search

   Finding the longest word with all prefixes present is easier using Trie traversal.

3. Final Answer:

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

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 is the correct way to declare a Trie node class in C# for storing children nodes?

easy

A. public class TrieNode { public Dictionary Children = new Dictionary(); public bool IsWord = false; }

B. public class TrieNode { public List<char> Children; public bool IsWord; }

C. public class TrieNode { public char[] Children = new char[26]; public bool IsWord; }

D. public class TrieNode { public int ChildrenCount; public bool IsWord; }

Solution

1. Step 1: Check children storage type

   Using a Dictionary allows dynamic children mapping by character.

2. Step 2: Confirm boolean flag for word end

   IsWord marks if node completes a valid word.

3. Final Answer:

   public class TrieNode { public Dictionary Children = new Dictionary(); public bool IsWord = false; } -> Option A

4. Quick Check:

   Dictionary + IsWord = correct TrieNode [OK]

Hint: Use Dictionary for flexible children [OK]

Common Mistakes:

• Using List<char> instead of mapping to nodes
• Using char array without node references
• Missing IsWord flag

3. Given the following code snippet, what will be the output?

var words = new string[] {"a", "app", "ap", "apply", "apple"};
var trie = new Trie();
foreach(var w in words) trie.Insert(w);
var longest = trie.FindLongestWord();
Console.WriteLine(longest);

Assuming FindLongestWord returns the longest word where all prefixes exist in the Trie.

medium

A. "ap"

B. "apply"

C. "apple"

D. "app"

Solution

1. Step 1: Insert all words into Trie

   Words inserted: "a", "app", "ap", "apply", "apple".

2. Step 2: Check prefixes for each word

   "apple" prefixes: "a", "ap", "app", "appl" ("appl" missing), so invalid.
   "apply" prefixes: "a", "ap", "app", "appl" ("appl" missing), invalid.
   "app" prefixes: "a", "ap", "app" all exist.
   "ap" prefixes: "a", "ap" exist but shorter than "app".

3. Final Answer:

   "app" -> Option D

4. Quick Check:

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

Hint: Check all prefixes exist for longest word [OK]

Common Mistakes:

• Assuming 'apple' or 'apply' are valid without all prefixes
• Ignoring prefix 'appl' missing
• Choosing shortest word instead

4. Identify the bug in this C# Trie insertion method snippet:

public void Insert(string word) {
  var node = root;
  foreach (char c in word) {
    if (!node.Children.ContainsKey(c))
      node.Children[c] = new TrieNode();
    node = node.Children[c];
    node.IsWord = true;
  }
}

medium

A. Setting IsWord = true inside the loop for every character

B. Not checking if root is null

C. Using foreach instead of for loop

D. Not initializing Children dictionary

Solution

1. Step 1: Analyze IsWord assignment

   IsWord should be true only at the end of the word, not for every character node.

2. Step 2: Identify correct placement

   IsWord = true must be set after the loop completes, marking the last node.

3. Final Answer:

   Setting IsWord = true inside the loop for every character -> Option A

4. Quick Check:

   IsWord only at word end [OK]

Hint: Set IsWord true only after full word insertion [OK]

Common Mistakes:

• Marking IsWord true too early
• Ignoring Children initialization
• Confusing loop types

5. You have a list of words: ["w", "wo", "wor", "worl", "world", "word", "worst"]. Using a Trie, which word will be returned as the longest word where all prefixes exist in the dictionary?

hard

A. "worst"

B. "word"

C. "world"

D. "worl"

Solution

1. Step 1: Check prefixes for each candidate

   "world" prefixes: "w", "wo", "wor", "worl", "world" all exist.
   "worst" prefixes: "w", "wo", "wor", "wors" (missing), invalid.
   "word" prefixes: "w", "wo", "wor", "word" all exist but shorter than "world".
   "worl" prefixes: "w", "wo", "wor", "worl" all exist but shorter.

2. Step 2: Choose longest valid word

   "world" is longest with all prefixes present.

3. Final Answer:

   "world" -> Option C

4. Quick Check:

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

Hint: Longest word with all prefixes present wins [OK]

Common Mistakes:

• Choosing 'worst' without 'wors' prefix
• Ignoring prefix checks
• Picking shorter words