-
Notifications
You must be signed in to change notification settings - Fork 16
/
SuffixTrieConstnruction.py
49 lines (42 loc) · 1.48 KB
/
SuffixTrieConstnruction.py
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
'''
Populate Suffix Trie:
Populate a suffix trie given a string
Implement a function that returns a boolean based on whether or not the
suffix trie contains the input string
Creation:
---------
Time: O(N^2) - Exponential
Space: O(N^2) - Linear (Alternate O(D), where D is the depth of the suffix trie)
Searching:
----------
Time: O(N) - Linear
Space: O(1) - Constant
Last Practiced: 2022-03-23 06:46:51
'''
# Do not edit the class below except for the
# populateSuffixTrieFrom and contains methods.
# Feel free to add new properties and methods
# to the class.
class SuffixTrie:
def __init__(self, string):
self.root = {}
self.endSymbol = "*"
self.populateSuffixTrieFrom(string)
def populateSuffixTrieFrom(self, string):
for i in range(len(string)):
self.insertCharacterAtIndex(i, string)
def insertCharacterAtIndex(self, index, string):
currentNode = self.root
for i in range(index,len(string)):
currentChar = string[i]
if currentChar not in currentNode:
currentNode[currentChar] = {}
currentNode = currentNode[currentChar]
currentNode[self.endSymbol] = True
def contains(self, string):
currentNode = self.root
for char in string:
if char not in currentNode:
return False
currentNode = currentNode[char]
return self.endSymbol in currentNode