Daily Coding Problem - 11

day-11.py

"""
This problem was asked by Twitter.

Implement an autocomplete system. That is, given a query string s and a set of all possible query strings, return all strings in the set that have s as a prefix.

For example, given the query string de and the set of strings [dog, deer, deal], return [deer, deal].

Hint: Try preprocessing the dictionary into a more efficient data structure to speed up queries.
"""
class Node:
    def __init__(self):
        self.children = [None]*26
        self.isEnd = False

class Trie:
    def __init__(self):
        self.root = Node()

    def addWord(self, word):
        curr = self.root
        for letter in word:
            index = ord(letter) - ord('a')
            if curr.children[index] is None:
                curr.children[index] = Node()
            curr = curr.children[index]
        curr.isEndOfWord = True

    def search(self, word):
        curr = self.root
        for letter in word:
            index = ord(letter) - ord('a')
            if curr.children[index] is None:
                return False
            curr = curr.children[index]
        if curr.isEndOfWord:
            return True
        else:
            return False

words = ["deer", "dear", "deal", "deep", "dead", "dean"]

trie = Trie()
for word in words:
    trie.addWord(word)

print(trie.search("deal"))
print(trie.search("deat"))