Longest Word in Dictionary Using Trie in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert a word into the Trie.

DSA C++

void insert(string word) {
    TrieNode* node = root;
    for (char c : word) {
        int index = c - 'a';
        if (node->children[[1]] == nullptr) {
            node->children[index] = new TrieNode();
        }
        node = node->children[index];
    }
    node->isEnd = true;
}

Drag options to blanks, or click blank then click option'

Aindex

Bc

Cword

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Using the character 'c' directly as an index causes errors.

Using the whole word instead of the character index.

We calculate the index of the character in the children array using 'index'. So, the blank should be filled with 'index'.

2fill in blank

medium

Complete the code to check if a node marks the end of a word.

DSA C++

bool isEndOfWord(TrieNode* node) {
    return node->[1];
}

Drag options to blanks, or click blank then click option'

AwordEnd

BisWord

Cend

DisEnd

Attempts:

3 left

💡 Hint

Common Mistakes

Using incorrect variable names like 'isWord' or 'wordEnd'.

The TrieNode uses 'isEnd' boolean to mark the end of a word.

3fill in blank

hard

Fix the error in the DFS function to find the longest word.

DSA C++

void dfs(TrieNode* node, string& current, string& longest) {
    if (!node || !node->[1]) return;
    if (current.length() > longest.length()) {
        longest = current;
    }
    for (int i = 0; i < 26; i++) {
        if (node->children[i] && node->children[i]->isEnd) {
            current.push_back('a' + i);
            dfs(node->children[i], current, longest);
            current.pop_back();
        }
    }
}

Drag options to blanks, or click blank then click option'

AisWord

BisEnd

Cend

DwordEnd

Attempts:

3 left

💡 Hint

Common Mistakes

Checking the wrong variable for word end.

Not stopping DFS when node is null.

The DFS should stop if the current node is not the end of a word, so we check 'isEnd'.

4fill in blank

hard

Fill both blanks to build the longest word using DFS traversal.

DSA C++

void dfs(TrieNode* node, string& current, string& longest) {
    if (!node || !node->[1]) return;
    if (current.length() > longest.length() || (current.length() == longest.length() && current < longest)) {
        longest = current;
    }
    for (int i = 0; i < 26; i++) {
        if (node->children[i] && node->children[i]->[2]) {
            current.push_back('a' + i);
            dfs(node->children[i], current, longest);
            current.pop_back();
        }
    }
}

Drag options to blanks, or click blank then click option'

AisEnd

BisWord

Cend

DwordEnd

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variable names for the two blanks.

Using variables that do not exist in the TrieNode.

Both blanks check if the node marks the end of a word using 'isEnd'.

5fill in blank

hard

Fill all three blanks to complete the function that finds the longest word in the dictionary.

DSA C++

string longestWord(vector<string>& words) {
    Trie trie;
    for (auto& word : words) {
        trie.[1](word);
    }
    string longest = "";
    string current = "";
    trie.[2](trie.root, current, longest);
    return longest;
}

class Trie {
public:
    TrieNode* root;
    Trie() {
        root = new TrieNode();
    }
    void [3](string word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (!node->children[index]) {
                node->children[index] = new TrieNode();
            }
            node = node->children[index];
        }
        node->isEnd = true;
    }
    void dfs(TrieNode* node, string& current, string& longest) {
        if (!node || !node->isEnd) return;
        if (current.length() > longest.length() || (current.length() == longest.length() && current < longest)) {
            longest = current;
        }
        for (int i = 0; i < 26; i++) {
            if (node->children[i] && node->children[i]->isEnd) {
                current.push_back('a' + i);
                dfs(node->children[i], current, longest);
                current.pop_back();
            }
        }
    }
};

Drag options to blanks, or click blank then click option'

Ainsert

Bdfs

CinsertWord

Dsearch

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'search' instead of 'insert' to add words.

Confusing function names for DFS.

We insert words using 'insert', start DFS with 'dfs', and the insert function is named 'insert'.