Daily-coding-problem/Daily_coding_problem_11.py at master · Orbedi/Daily-coding-problem · GitHub

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
""" Problem:
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].

"""


class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


class Tree:
    def __init__(self):
        self.root = None

    def insert(self, tree, data):
        if tree is None:
            tree = Node(data)
        else:
            current = tree.value
            if current > data:
                tree.left = self.insert(tree.left, data)
            else:
                tree.right = self.insert(tree.right, data)
        return tree

    def search(self, tree, data, result):
        if tree is None:
            return
        else:
            if data == tree.value[0:len(data)]:
                result.append(tree.value)
                self.search(tree.left, data, result)
                self.search(tree.right, data, result)
            elif data < tree.value:
                self.search(tree.left, data, result)
            else:
                self.search(tree.right, data, result)


def prefix(list_, prfx):
    tree = Tree()
    for item in list_:
        tree.root = tree.insert(tree.root, item)
    result = []
    tree.search(tree.root, prfx, result)
    return result


if __name__ == '__main__':
    list_ = ['aaa', 'bbb', 'ccc', 'dog', 'deer', 'home', 'car', 'deal', 'aba', 'dezf']
    list_2 = ['ccc', 'bba', 'baa', 'dde', 'ddd']
    list_3 = ['ccc', 'cbba', 'cbaa', 'cdde', 'cddd']
    list_4 = []

    assert prefix(list_,'de') == ['deer', 'deal', 'dezf']
    assert prefix(list_2,'b') == ['bba', 'baa']
    assert prefix(list_3,'c') == ['ccc', 'cbba', 'cbaa', 'cdde', 'cddd']
    assert prefix(list_3,'cd') == ['cdde', 'cddd']
    assert prefix(list_4,'prueba') == []