Category: trie
-
LeetCode 386: Lexicographical Numbers
link String sort Since there are digits in a number, time: , space: . DFS in a Trie There are digits in a number. So, building the trie and a DFS of the trie, both take time . Time: , space: . DFS in implicit Trie We could traverse the trie without explicitly building it.…
-
LeetCode 1065: Index Pairs of a String
link Substrings For each of the substrings, check if it is in the word_set. Say , , and the longest word has length . Time: , space: . Trie If a word is in the text, the word is a prefix of a suffix of the text. Since the text has only suffixes, from a…
-
LeetCode 14: Longest Common Prefix
link At an index, if all strings have the same character, set of these characters will have length one. Say there are strings and the shortest string has length . There are iterations. In each iteration both collecting characters at a given index and creating the set takes time . Time: , space: .
-
LeetCode 692: Top K Frequent Words
link Sorted frequency map We first create the frequency map: {word: count}. We then sort the map items with (- count) as the primary key and word as the secondary key. Finally, we return the first k of these sorted words as the answer. Assuming word comparison cost as constant, If there are words, time:…
-
LeetCode 212: Word Search II
link Backtrack For each word, we can search if it is in the board with backtracking. Trie We can build a trie out of the words to search, excluding a word if its first char does not appear in the board. While collecting words from the trie, we check against the board to see if…
-
LeetCode 211: Design Add and Search Words Data Structure
link Trie If word has “.”, we follow all available edges. Say the longest word has length . Operation Time Space insert search If there are no dots: . If all are dots: . Other cases should be in-between.
-
LeetCode 648: Replace Words
link Sort and search If we sort the dictionary, the first root that is a prefix of a word should be used to replace that word. To make the search efficient, we can binary-search the insert position of word[0] in the sorted dictionary and thereon we do linear-search. Say , the longest root has length…
-
LeetCode 1268: Search Suggestions System
link The question is a bit misleading. From the description, it feels like the lexicographical sorting should be applicable only if there are more than three products, which is not the case. As long as there are more than one suggestions, we must emit them in lexicographic order capping at three suggestions. Sort and search…
-
LeetCode 208: Implement Trie (Prefix Tree)
link We represent the Trie as a tree with TrieNode‘s. An edge has two end points and a label: . Following an edge, , consumes the word character, . If a node is reached consuming the last character of a word, that node is marked with end_of_word = True. The root is a special node,…
unreasonably effective 