# how to solve this problem using trie? thanks

• If a string is matched to any filter, it is in the black list, otherwise not.
Design a data structure and implement following two functions.

isInBlackList(string)

filters having at most one star * , which matches 0 or more chars.

• Build a trie to keep all filter string, and search trie as normal trie.
If search fail and there is * in the trie, search the suffix of search string.
If any suffix match in the trie node of * means matched.
Here is my python solution,

class StringFilter():
def init(self):
self.trie = {}

``````def add_to_trie(self, s):
node = self.trie
for c in s:
if c not in node:
node[c] = {}
node = node[c]
node["\$"] = s

def search_trie(self, s, node):
if not s:
return "\$" in node
if s[0] in node:
return self.search_trie(s[1:], node[s[0]])
elif "*" in node:
for i in xrange(len(s) + 1):# i is the number of char represented by *
if self.search_trie(s[i:], node["*"]):
return True
return False
else:
return False

def isBlackList(self, s):
return self.search_trie(s, self.trie)
``````

filt = StringFilter()
")
s = "abc"
print(s, filt.isBlackList(s))
s = "cbd"
print(s, filt.isBlackList(s))
s = "cbaer"
print(s, filt.isBlackList(s))
s = "cbaefasdwer"
print(s, filt.isBlackList(s))
s = "ert"
print(s, filt.isBlackList(s))
s = "erteererer"
print(s, filt.isBlackList(s))

• Should be doable in O(n^2)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.