Trie (Digital/Prefix tree) Strategies

Question 1

Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.

Example:

Trie trie = new Trie();

trie.insert("apple");

trie.search("apple"); // returns true

trie.search("app"); // returns false

trie.startsWith("app"); // returns true

trie.insert("app");

trie.search("app"); // returns true

Note:

• You may assume that all inputs are consist of lowercase letters a-z.
• All inputs are guaranteed to be non-empty strings.

Answer 1

Insertion of a key to a trie

We insert a key by searching into the trie. We start from the root and search a link, which corresponds to the first key character. There are two cases :

• A link exists. Then we move down the tree following the link to the next child level. The algorithm continues with searching for the next key character.
• A link does not exist. Then we create a new node and link it with the parent’s link matching the current key character. We repeat this step until we encounter the last character of the key, then we mark the current node as an end node and the algorithm finishes.

Complexity Analysis: Time complexity: O(m). Space complexity: O(m).

Search for a key in a trie

Each key is represented in the trie as a path from the root to the internal node or leaf. We start from the root with the first key character. We examine the current node for a link corresponding to the key character. There are two cases :

• A link exist. We move to the next node in the path following this link, and proceed searching for the next key character.
• A link does not exist. If there are no available key characters and current node is marked as isEnd we return true. Otherwise there are possible two cases in each of them we return false :
  
  • There are key characters left, but it is impossible to follow the key path in the trie, and the key is missing.
  • No key characters left, but current node is not marked as isEnd. Therefore the search key is only a prefix of another key in the trie.

Complexity Analysis: Time complexity: O(m), Space complexity: O(1)

Search for a key prefix in a trie

The approach is very similar to the one we used for searching a key in a trie. We traverse the trie from the root, till there are no characters left in key prefix or it is impossible to continue the path in the trie with the current key character. The only difference with the mentioned above search for a key algorithm is that when we come to an end of the key prefix, we always return true. We don’t need to consider the isEnd mark of the current trie node, because we are searching for a prefix of a key, not for a whole key.

Complexity Analysis: Time complexity: O(m). Space complexity: O(1)

Question 2

Add and Search Word - Data structure design

Answer 2

-

Question 3

Word Search II / Boggle

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example:

Input: board = [[‘o’,’a’,’a’,’n’], [‘e’,’t’,’a’,’e’], [‘i’,’h’,’k’,’r’], [‘i’,’f’,’l’,’v’] ]

words = ["oath","pea","eat","rain"]Output: ["eat","oath"]

Note:

• All inputs are consist of lowercase letters a-z.
• The values of words are distinct.

Answer 3

The overall workflow of the algorithm is intuitive, which consists of a loop over each cell in the board and a recursive function call starting from the cell. Here is the skeleton of the algorithm.

• We build a Trie out of the words in the dictionary, which would be used for the matching process later.
• Starting from each cell, we start the backtracking exploration (i.e. backtracking(cell)), if there exists any word in the dictionary that starts with the letter in the cell.
• During the recursive function call backtracking(cell), we explore the neighbor cells (i.e. neighborCell) around the current cell for the next recursive call backtracking(neighborCell). At each call, we check if the sequence of letters that we traverse so far matches any word in the dictionary, with the help of the Trie data structure that we built at the beginning.

Question 4

Palindrome Pairs

Answer 4

https://leetcode.com/problems/palindrome-pairs/

Question 5

Maximum XOR of Two Numbers in an Array

Answer 5

https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/

Question 6

Word Squares

Answer 6

https://leetcode.com/problems/design-search-autocomplete-system/

Question 7

Concatenated Words

Answer 7

-

Question 8

Design Search Autocomplete System

Answer 8

https://leetcode.com/problems/design-search-autocomplete-system/

Question 9

Replace Words

Answer 9

-

Question 10

Implement Magic Dictionary

Answer 10

-

Question 11

Map Sum Pairs

Answer 11

-

Question 12

Top K Frequent Words

Answer 12

-

Question 13

Longest Word in Dictionary

Answer 13

-

Question 14

Prefix and Suffix Search

Answer 14

-

Question 15

Index Pairs of a String

Answer 15

-

Question 16

Camelcase Matching

Answer 16

-

Question 17

Stream of Characters

Implement the StreamChecker class as follows:

• StreamChecker(words): Constructor, init the data structure with the given words.
• query(letter): returns true if and only if for some k >= 1, the last k characters queried (in order from oldest to newest, including this letter just queried) spell one of the words in the given list.

Answer 17

1. Build a trie using the reversed words.
2. Keep track of the queried letters.
3. Check if the reverse of the queried string is in the trie.