interview_prep/208.py at main · rishsanyal/interview_prep · 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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
class Node(object):
    def __init__(self, letter=None):
        self.letter = letter
        self.next = {}


class Trie(object):
    def __init__(self):
        # self.tracker = set()
        self.starter = Node("#")

    def insert(self, word):
        """
        :type word: str
        :rtype: None
        """
        # self.tracker.add(word)

        curr_char = "#"
        word_len = 0 #, len(word)

        curr_node = self.starter

        while word_len < len(word) and word[word_len] in curr_node.next:
            curr_node = curr_node.next[word[word_len]]
            word_len += 1

        while word_len < len(word):
            curr_node.next[word[word_len]] = Node(word[word_len])
            curr_node = curr_node.next[word[word_len]]
            word_len += 1

        curr_node.next['#'] = Node("#")

        return

    def printAll(self):
        nodes = [self.starter]

        while nodes:
            curr_node = nodes.pop()

            print(curr_node.letter)

            nodes.extend(curr_node.next.values())


    def search(self, word):
        """
        :type word: str
        :rtype: bool
        """

        word_len = 0
        curr_node = self.starter

        while word_len < len(word):
            if word[word_len] not in curr_node.next.keys():
                return False

            curr_node = curr_node.next[word[word_len]]
            word_len += 1

        return ("#" in curr_node.next)


    def startsWith(self, prefix):
        """
        :type prefix: str
        :rtype: bool
        """

        word_len = 0
        curr_node = self.starter

        while word_len < len(prefix):
            if prefix[word_len] not in curr_node.next.keys():
                break

            curr_node = curr_node.next[prefix[word_len]]
            word_len += 1

        # print(word_len)
        # print(len(prefix) - 1)

        return word_len == len(prefix)


# Your Trie object will be instantiated and called as such:
obj = Trie()
obj.insert("apple")
# obj.insert("terror")
# obj.printAll()
param_2 = obj.search("apple")
print(param_2)

param_2 = obj.search("app")
print(param_2)

param_3 = obj.startsWith("b")
print(param_3)