Word Search in Trie in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert a word into the Trie.

DSA Go

func (t *Trie) Insert(word string) {
    node := t.root
    for _, ch := range word {
        if node.children[ch] == nil {
            node.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
        }
        node = node.children[ch]
    }
    node.isWord = [1]
}

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

Atrue

Bnil

Cfalse

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Setting node.isWord to false instead of true.

Forgetting to mark the end of the word.

Marking node.isWord as true indicates the end of a valid word in the Trie.

2fill in blank

medium

Complete the code to check if a word exists in the Trie.

DSA Go

func (t *Trie) Search(word string) bool {
    node := t.root
    for _, ch := range word {
        if node.children[ch] == nil {
            return [1]
        }
        node = node.children[ch]
    }
    return node.isWord
}

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

Anil

Btrue

Cfalse

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Returning true when a character is missing.

Not checking if the node marks the end of a word.

If a character path is missing, the word does not exist, so return false.

3fill in blank

hard

Fix the error in the code to correctly check if a prefix exists in the Trie.

DSA Go

func (t *Trie) StartsWith(prefix string) bool {
    node := t.root
    for _, ch := range prefix {
        if node.children[ch] == [1] {
            return false
        }
        node = node.children[ch]
    }
    return true
}

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

Anil

Btrue

Cfalse

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing to true or false instead of nil.

Returning true when the prefix path is missing.

We check if the child node is nil to know if the prefix path exists.

4fill in blank

hard

Fill both blanks to complete the recursive helper function for word search in a 2D board using Trie.

DSA Go

func dfs(board [][]byte, node *TrieNode, i, j int, path string, result *map[string]bool) {
    if i < 0 || i >= len(board) || j < 0 || j >= len(board[0]) || board[i][j] == '#' {
        return
    }
    ch := rune(board[i][j])
    nextNode := node.children[[1]]
    if nextNode == nil {
        return
    }
    path += string([2])
    if nextNode.isWord {
        (*result)[path] = true
    }
    board[i][j] = '#'
    dfs(board, nextNode, i+1, j, path, result)
    dfs(board, nextNode, i-1, j, path, result)
    dfs(board, nextNode, i, j+1, path, result)
    dfs(board, nextNode, i, j-1, path, result)
    board[i][j] = byte(ch)
}

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

Ach

Bi

Cj

Dpath

Attempts:

3 left

💡 Hint

Common Mistakes

Using indices i or j instead of the character.

Using the path string instead of the character.

We use the current character 'ch' to move to the next Trie node in children map.

5fill in blank

hard

Fill all three blanks to complete the function that builds a map of found words from the board using Trie.

DSA Go

func findWords(board [][]byte, words []string) []string {
    trie := NewTrie()
    for _, word := range words {
        trie.Insert([1])
    }
    result := make(map[string]bool)
    for i := 0; i < len(board); i++ {
        for j := 0; j < len(board[0]); j++ {
            dfs(board, trie.root, i, j, [2], &result)
        }
    }
    res := []string{}
    for word := range result {
        res = append(res, [3])
    }
    return res
}

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

Aword

B""

Cnil

Dboard

Attempts:

3 left

💡 Hint

Common Mistakes

Passing nil or board instead of the word to Insert.

Starting DFS with nil or board instead of empty string.

Insert each word into the Trie, start DFS with empty path string, and pass the Trie root node.