Teaching Kids Programming – Search Engine Algorithm (Word Matching) using Trie (Prefix Tree) and Depth First Search

Teaching Kids Programming: Videos on Data Structures and Algorithms

Implement a data structure with the following methods:

• add(String word) which adds a lowercase alphabet string word to the search engine.
• exists(String word) which checks if word is in the engine. word may contain “.” which means to match any character.

Constraints
k ≤ 1,000 where k is the length of word
n ≤ 100,000 where n is the number of calls to add and exists
Example 1
Input
methods = [“constructor”, “add”, “add”, “exists”, “exists”, “exists”]
arguments = [[], [“dog”], [“document”], [“dog”], [“do.”], [“….”]]`
Output
[None, None, None, True, True, False]

Search Engine Algorithm: Searching a Word using Depth First Search Algorithm in Prefix Tree (Trie)

We build the words into a Prefix Tree (Trie) so that we can achieve O(N) time (N is the length of the word) for search a word or prefix in the list. Without Trie or Prefix Tree, if we bruteforce, the search takes O(M*N) because we have to check M words and compare each word in the worst N times. If we store the M words in a hash table/set, we can look up exact match in O(1) constant time. However, it does not help in searching a prefix existence.

THe “.” matches any characters, and we can start Depth First Search Algorithm for the children nodes of current Trie Node. To do this, we add extra parameter to the search function to specify which Trie Node (as a new Root) to start with.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

class Trie:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.data = {}
        self.isLeaf = False
 
    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        cur = self
        for i in word:
            if not i in cur.data:
                cur.data[i] = Trie()
            cur = cur.data[i]
        cur.isLeaf = True                        
 
    def dfs(self, word, root = None) -> bool:
        if not root:
            root = self
        for i, c in enumerate(word):
            if c == '.':
                for a in root.data:
                    if self.dfs(word[i + 1:], root.data[a]):
                        return True
                return False
            elif c in root.data:
                root = root.data[c]
            else:
                return False
        return root.isLeaf
 
class SearchEngine:
    def __init__(self):
        self.words = Trie()
 
    def add(self, word):
        self.words.insert(word)
 
    def exists(self, word):
        return self.words.dfs(word)        

class Trie:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.data = {}
        self.isLeaf = False
 
    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        cur = self
        for i in word:
            if not i in cur.data:
                cur.data[i] = Trie()
            cur = cur.data[i]
        cur.isLeaf = True                        

    def dfs(self, word, root = None) -> bool:
        if not root:
            root = self
        for i, c in enumerate(word):
            if c == '.':
                for a in root.data:
                    if self.dfs(word[i + 1:], root.data[a]):
                        return True
                return False
            elif c in root.data:
                root = root.data[c]
            else:
                return False
        return root.isLeaf

class SearchEngine:
    def __init__(self):
        self.words = Trie()

    def add(self, word):
        self.words.insert(word)

    def exists(self, word):
        return self.words.dfs(word)        

–EOF (The Ultimate Computing & Technology Blog) —