Trie Flashcards
Implement a Prefix tree, which someone to easily check if a word has been previously inserted, or if a previously inserted word starts with a specific prefix
The idea is that you create a tree with the root just being an empty node. All child nodes consist of a singular character.
So if you’re checking if a word exists, you start at the root node and check if the first letter of the word is the value of one of the child nodes of the root, and so on.
You have to have a boolean flag on each node to see if it marks the end of an inserted word.
So create a node class that can efficiently check if any of a nodes child nodes have a specific value.
Design a word search datastructure that lets you add words and search if a word exists. Add support for the use of a wildcard character (i.e. the user can search for “s*y” where the existence of any three letter word starting with ‘s’ and ending in ‘y’ would result in a return value of True)
We use a prefix tree here. The real meat of the problem is the search function. There we must use a backtracking approach on account of the wildcards. When we have a wildcard, we must consider each of the current nodes children as a starting point, and backtrack if it doesn’t work out.
Word Search II: Given a m*n board of characters and a list of words, return a sublist of those words that are actually present in the board. To make a word, you can start from any square and go to any adjacent squares over and over ( can’t reuse a square).
This is similar to regular word search so we could just repeat that algorithm for each word provided to get our list. For efficiency though, we can use a prefix tree. We will initially build a prefix tree with the given list of words. We can then add a node parameter to our dfs. If we are ever in a position where board[r][c] isn’t part of “node’s” children, we can return as we know there is no possibility of creating a word going down this path. Otherwise, we know that this represents a potential path and so we get the appropriate child node for the current char. If that child node’s isWord property is true, we have found a word. This is the mechanism used to add words to a list of found words.
