Catalog:
LC 745 [Prefix and Suffix Search]
LC 676 [Implement Magic Dictionary]
LC 208 Implement Trie (Prefix Tree)
LC 211 Add and Search Word -- Data Structure Design
[Uber] 642 Design Search Autocomplete System
[Uber]LC 745 Prefix and Suffix Search
Method 1: build all possible prefix and suffix combination in a dictionary and words with higher weight will overwrite the previous record. This is for quick look up!
class WordFilter(object):
def __init__(self, words):
self.d = {}
for index, word in enumerate(words):
prefix = ''
for char in [''] + list(word):
prefix += char
suffix = ''
for char in [''] + list(word[::-1]):
suffix += char
self.d[prefix + '.' + suffix[::-1]] = index
def f(self, prefix, suffix):
return self.d.get(prefix + '.' + suffix, -1)
Store pre and suffix, look up is slower but it is quicker to build
class WordFilter(object):
def __init__(self, words):
self.prefix=defaultdict(set)
self.suffix=defaultdict(set)
self.ind={}
for i,w in enumerate(words):
self.ind[w]=i
n=len(w)
for i in range(n+1):
self.prefix[w[:i]].add(w)
self.suffix[w[n-i:]].add(w)
def f(self, prefix, suffix):
pool=self.prefix[prefix]&self.suffix[suffix]
return max(self.ind[w] for w in pool) if pool else -1
Not using Trie Structure could lead a very big space complexity when N is very big. Trie would be recommended to save space and get O(L) find time complexity!
The way we will look up the Trie is using combination of prefix and suffix, for example, pre + '#' + suf. That's what we are going to insert when we get a word
TrieNode should have a field called weight, and a method to insert new pair.
LC 676 Implement Magic Dictionary
Trie (we pronounce "try") or prefix tree is a tree data structure, which is used for retrieval of a key in a dataset of strings. There are various applications of this very efficient data structure such as : Autocomplete, Spell checker, IP routing (Longest prefix matching), T9 predictive text, Solving word games.
There are several other data structures, like balanced trees and hash tables, which give us the possibility to search for a word in a dataset of strings. Then why do we need trie? Although hash table has O(1)O(1)O(1) time complexity for looking for a key, it is not efficient in the following operations :
?Finding all keys with a common prefix.
?Enumerating a dataset of strings in lexicographical order.
Trie could use less space compared to Hash Table when storing many keys with the same prefix. In this case using trie has only O(m) time complexity, where m is the key length. Searching for a key in a balanced tree costs O(mlogn) time complexity.
LC 208 Implement Trie (Prefix Tree)
Implement a trie with insert, search, and startsWith methods.
class TrieNode(object):
def __init__(self):
self.is_word = False
self.children = collections.defaultdict(TrieNode)
class Trie(object):
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for c in word:
node = node.children[c]
node.is_word = True
def search(self, word, search_word=True):
node = self.root
for c in word:
if c not in node.children:
return False
node = node.children[c]
return node.is_word if search_word else True
def startsWith(self, prefix):
return self.search(prefix, False)
LC 211 Add and Search Word -- Data Structure Design
Implement a class called WordDictionary with add and search methods. Search(word) can search a literal word or a regular expression string containing only letters a-z or . (any one letter).
Hash table and bucket by len(word) -- collision if the word length are the same or quite gather together. So if we only need to add and search, and we do not need frequency counting, it is definitely better to use Trie.
