Practice - 5 Tasks
Answer the questions below
1fill in blank
easyComplete 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'
Attempts:
3 left
💡 Hint
Common Mistakes
Setting node.isWord to false instead of true.
Forgetting to mark the end of the word.
✗ Incorrect
Marking node.isWord as true indicates the end of a valid word in the Trie.
2fill in blank
mediumComplete 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'
Attempts:
3 left
💡 Hint
Common Mistakes
Returning true when a character is missing.
Not checking if the node marks the end of a word.
✗ Incorrect
If a character path is missing, the word does not exist, so return false.
3fill in blank
hardFix 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'
Attempts:
3 left
💡 Hint
Common Mistakes
Comparing to true or false instead of nil.
Returning true when the prefix path is missing.
✗ Incorrect
We check if the child node is nil to know if the prefix path exists.
4fill in blank
hardFill 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'
Attempts:
3 left
💡 Hint
Common Mistakes
Using indices i or j instead of the character.
Using the path string instead of the character.
✗ Incorrect
We use the current character 'ch' to move to the next Trie node in children map.
5fill in blank
hardFill 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'
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.
✗ Incorrect
Insert each word into the Trie, start DFS with empty path string, and pass the Trie root node.