Tries

A **prefix tree** (also known as a trie) is a tree data structure used to efficiently store and retrieve keys in a set of strings. Some applications of this data structure include auto-complete and spell checker systems. Implement the PrefixTree class: * `PrefixTree()` Initializes the prefix tree object. * `void insert(String word)` Inserts the string `word` into the prefix tree. * `boolean search(String word)` Returns `true` if the string `word` is in the prefix tree (i.e., was inserted before), and `false` otherwise. * `boolean startsWith(String prefix)` Returns `true` if there is a previously inserted string `word` that has the prefix `prefix`, and `false` otherwise. **Example 1:** ```java Input: ["Trie", "insert", "dog", "search", "dog", "search", "do", "startsWith", "do", "insert", "do", "search", "do"] Output: [null, null, true, false, true, null, true] Explanation: PrefixTree prefixTree = new PrefixTree(); prefixTree.insert("dog"); prefixTree.search("dog"); // return true prefixTree.search("do"); // return false prefixTree.startsWith("do"); // return true prefixTree.insert("do"); prefixTree.search("do"); // return true ``` **Constraints:** * `1 <= word.length, prefix.length <= 1000` * `word` and `prefix` are made up of lowercase English letters. <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n)</code> time for each function call and <code>O(t)</code> space, where <code>n</code> is the length of the given string and <code>t</code> is the total number of nodes created in the Trie. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A Trie is structured as a tree-like data structure where each node contains a hash map (or an array for fixed character sets) to store references to its child nodes, which represent characters. Each node also includes a boolean flag to indicate whether the current node marks the end of a valid word. The Trie starts with a root node that does not hold any character and serves as the entry point for all operations. The child nodes of the root and subsequent nodes represent unique characters from the words stored in the Trie, forming a hierarchical structure based on the prefixes of the words. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> To insert a word, we iterate through the characters of the word with index <code>i</code>, starting at the root of the Trie as the current node. If the current node already contains <code>word[i]</code>, we continue to the next character and move to the node that <code>word[i]</code> points to. If <code>word[i]</code> is not present, we create a new node for <code>word[i]</code> and continue the process until we reach the end of the word. We mark the boolean variable as true as it is the end of the inserted word. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> Searching for a word is similar to inserting, but instead of creating new nodes, we return <code>false</code> if we don't find a character in the path while iterating or if the end-of-word marker is not set to <code>true</code> when we reach the end of the word. </p> </details>

Design a data structure that supports adding new words and searching for existing words. Implement the `WordDictionary` class: * `void addWord(word)` Adds `word` to the data structure. * `bool search(word)` Returns `true` if there is any string in the data structure that matches `word` or `false` otherwise. `word` may contain dots `'.'` where dots can be matched with any letter. **Example 1:** ```java Input: ["WordDictionary", "addWord", "day", "addWord", "bay", "addWord", "may", "search", "say", "search", "day", "search", ".ay", "search", "b.."] Output: [null, null, null, null, false, true, true, true] Explanation: WordDictionary wordDictionary = new WordDictionary(); wordDictionary.addWord("day"); wordDictionary.addWord("bay"); wordDictionary.addWord("may"); wordDictionary.search("say"); // return false wordDictionary.search("day"); // return true wordDictionary.search(".ay"); // return true wordDictionary.search("b.."); // return true ``` **Constraints:** * `1 <= word.length <= 20` * `word` in `addWord` consists of lowercase English letters. * `word` in `search` consist of `'.'` or lowercase English letters. * There will be at most `2` dots in `word` for `search` queries. * At most `10,000` calls will be made to `addWord` and `search`. <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n)</code> time for each function call and <code>O(t + n)</code> space, where <code>n</code> is the length of the string and <code>t</code> is the total number of nodes created in the Trie. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute force solution would be to store each added word in a list and search linearly through the list for a word every time. This would be an <code>O(m * n)</code> solution, where <code>m</code> is the size of the list and <code>n</code> is the length of the string. Can you think of a better way? Maybe there is a tree-like data structure. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We can use a Trie to implement adding and searching for words efficiently. Adding a word follows the standard Trie insertion process. However, when searching for a word containing <code>'.'</code>, which can match any character, we need a different approach. Instead of directly matching, we consider all possible characters at the position of <code>'.'</code> and recursively check the rest of the word for each possibility. How would you implement it? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We traverse the word with index <code>i</code>, starting at the root of the Trie. For normal characters, we search as usual. When encountering a dot (<code>'.'</code>), we try all possible characters by recursively extending the search in each direction. If any path leads to a valid word, we return <code>true</code>; otherwise, we return <code>false</code>. Although we try all paths for a dot, the time complexity is still <code>O(n)</code> because there are at most two dots (<code>'.'</code>) in the word, making the complexity <code>O((26^2) * n)</code>. </p> </details>

Given a 2-D grid of characters `board` and a list of strings `words`, return all words that are present in the grid. Give any solution out of multiple solutions For a word to be present it must be possible to form the word with a path in the board with horizontally or vertically neighboring cells. The same cell may not be used more than once in a word. **Example 1:**  ```java Input: board = [ ["a","b","c","d"], ["s","a","a","t"], ["a","c","k","e"], ["a","c","d","n"] ], words = ["bat","cat","back","backend","stack"] Output: ["cat","back","backend"] ``` **Example 2:**  ```java Input: board = [ ["x","o"], ["x","o"] ], words = ["xoxo"] Output: [] ``` **Constraints:** * `1 <= board.length, board[i].length <= 12` * `board[i]` consists only of lowercase English letter. * `1 <= words.length <= 30,000` * `1 <= words[i].length <= 10` * `words[i]` consists only of lowercase English letters. * All strings within `words` are distinct. <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(m * n * 4 * (3^(t-1)) + s)</code> time and <code>O(s)</code> space, where <code>m</code> is the number of rows, <code>n</code> is the number of columns, <code>t</code> is the maximum length of any word and <code>s</code> is the sum of the lengths of all the words. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> To search for a word in the grid, we can use backtracking by starting at each cell, simultaneously iterating through the word and matching the characters with the cells, recursively visiting the neighboring cells. However, if we are given a list of words and need to search for each one, it becomes inefficient to iterate through each word and run backtracking for each. Can you think of a better way? Perhaps a data structure could help with more efficient word search and insertion. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We can use a Trie to efficiently search for multiple words. After inserting all words into the Trie, we traverse the grid once. For each character in the grid, we check if it exists in the current Trie node. If not, we prune the search. If we encounter an "end of word" flag in the Trie node, we know a valid word has been found. But how can we add that word to the result list? Maybe you should think about what additional information you can store in the Trie node. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> When we insert a word into the Trie, we can store the word's index. Why? Because when we want to add the word to the result list after finding a valid word, we can easily add it using the index. After adding that word, we put <code>index = -1</code> as we shouldn't add the word multiple times to the result list. How can you implement this? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> We insert all the words into the Trie with their indices marked. Then, we iterate through each cell in the grid. At each cell, we start at the root of the Trie and explore all possible paths. As we traverse, we match characters in the cell with those in the Trie nodes. If we encounter the end of a word, we take the index at that node and add the corresponding word to the result list. Afterward, we unmark that index and continue exploring further paths. </p> </details>