Word Search in Trie in DSA Javascript - Build from Scratch

Word Search in Trie

📖 Scenario: Imagine 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.

🎯 Goal: You will create a Trie, add some words to it, and then write code to search for a specific word in the Trie.

📋 What You'll Learn

Create a Trie node structure using JavaScript objects

Insert given words into the Trie

Search for a given word in the Trie

Print true if the word exists, otherwise false

💡 Why This Matters

🌍 Real World

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

💼 Career

Understanding Tries helps in roles involving search optimization, text processing, and building efficient data retrieval systems.

1

Create the Trie root node

Create a variable called trie and set it to an empty object {} to represent the root node of the Trie.

DSA Javascript

# Your code here

Hint

The root node of a Trie is usually an empty object that will hold child nodes as keys.

2

Add a list of words to insert

Create a variable called words and set it to the array ["cat", "car", "dog"] which contains the words to add to the Trie.

DSA Javascript

const trie = {}
# Your code here

Hint

Use an array to hold the words you want to add to the Trie.

3

Insert words into the Trie

Write a for loop using word to go through each word in words. Inside the loop, use a variable node set to trie. Then, use another for loop with char to go through each character in word. For each char, if node[char] does not exist, set it to an empty object {}. Then update node to node[char]. After the inner loop, set node.isWord = true to mark the end of the word.

DSA Javascript

const trie = {};
const words = ["cat", "car", "dog"];
# Your code here

Hint

Think of the Trie as a tree where each character is a branch. Create branches if they don't exist and mark the end of a word.

4

Search for a word in the Trie and print result

Create a variable called searchWord and set it to "car". Then create a variable called node and set it to trie. Use a for loop with char to go through each character in searchWord. Inside the loop, if node[char] does not exist, print false and return. Otherwise, update node to node[char]. After the loop, print node.isWord === true.

DSA Javascript

const trie = {};
const words = ["cat", "car", "dog"];

for (const word of words) {
    let node = trie;
    for (const char of word) {
        if (!node[char]) {
            node[char] = {};
        }
        node = node[char];
    }
    node.isWord = true;
}

# Your code here

Hint

Follow the characters down the Trie. If any character is missing, the word is not found. If all characters are found and isWord is true, print true.