| Problem Names | Solution Writeups | Code |
|---|---|---|
| Implement Trie Prefix Tree |
The idea of trie is a prefix tree. Each TrieNode will contain a children list which will contain all the TrieNode it can go. So for an example of string, each character in the string will represent a TrieNode, So for example, the word "apple" will be a -> p -> p -> l -> e in a trie. Implement this, and for each node add one more boolean variable called isEndOfWord. This boolean == true only if current TrieNode is the end of the word. |
|
| Design Add and Search Word Data Structure |
Implement a trie and for inserting word, add it into the trie. To search the word, simply go through each TrieNode. To handle a '.', search all possible children (which is at most O(26) since duplicate characters will be store in the same TrieNode). |
|
| Word Search II |
The idea is that first construct a trie from the words array. Then for each position in the board, do dfs on the trie. To prevent revisited board[i][j], we can change the character on board[i][j] to some other character like '-'. But remember to change back at the end of the dfs function so that it gets restored and can be reused. This is important to pass test case like finding the word "hf" and "hlf". |