-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathTrie.py
More file actions
144 lines (120 loc) · 3.86 KB
/
Copy pathTrie.py
File metadata and controls
144 lines (120 loc) · 3.86 KB
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
# Created by Roshan Jayswal
# Copyright © 2021 AppMillers. All rights reserved.
from typing import List
class TrieNode:
def __init__(self):
self.children = {}
self.endOfString = False
self.words = list()
self.n = 0
class Trie:
def __init__(self):
self.root = TrieNode()
def insertString(self, word):
current = self.root
for i in word:
ch = i
node = current.children.get(ch)
if node == None:
node = TrieNode()
current.children.update({ch:node})
current = node
if node.n < 3:
node.words.append(word)
node.n += 1
current.endOfString = True
print("Successfully inserted")
def searchString(self, word):
currentNode = self.root
for i in word:
node = currentNode.children.get(i)
if node == None:
return False
currentNode = node
if currentNode.endOfString == True:
return True
else:
return False
def find_word_by_prefix(self, c):
if self.root and c in self.root.children:
self.root = self.root.children[c]
return self.root.words
else:
self.root = None
return []
class Solution:
def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
products.sort()
newTrie = Trie()
for word in products:
newTrie.insertString(word)
return [newTrie.find_word_by_prefix(c) for c in searchWord]
def deleteString(root, word, index):
ch = word[index]
currentNode = root.children.get(ch)
canThisNodeBeDeleted = False
if len(currentNode.children) > 1:
deleteString(currentNode, word, index+1)
return False
if index == len(word) - 1:
if len(currentNode.children) >= 1:
currentNode.endOfString = False
return False
else:
root.children.pop(ch)
return True
if currentNode.endOfString == True:
deleteString(currentNode, word, index+1)
return False
canThisNodeBeDeleted = deleteString(currentNode, word, index+1)
if canThisNodeBeDeleted == True:
root.children.pop(ch)
return True
else:
return False
"""
newTrie = Trie()
newTrie.insertString("App")
newTrie.insertString("Appl")
deleteString(newTrie.root, "App", 0)
print(newTrie.searchString("App"))
"""
sol = Solution()
products = ['mousepad', 'moneypot', 'monitor', 'mouse', 'mobile']
print(sol.suggestedProducts(products, "mouse"))
"""[Method 2]
"""
class TrieNode:
def __init__(self):
# Stores children nodes and whether node is the end of a word
self.children = {}
self.isEnd = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
cur = self.root
# Insert character by character into trie
for c in word:
# if character path does not exist, create it
if c not in cur.children:
cur.children[c] = TrieNode()
cur = cur.children[c]
cur.isEnd = True
def search(self, word: str) -> bool:
cur = self.root
# Search character by character in trie
for c in word:
# if character path does not exist, return False
if c not in cur.children:
return False
cur = cur.children[c]
return cur.isEnd
def startsWith(self, prefix: str) -> bool:
# Same as search, except there is no isEnd condition at final return
cur = self.root
for c in prefix:
if c not in cur.children:
return False
cur = cur.children[c]
return True