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.
addFilter(filter)
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 addFilter(self, filt):
self.add_to_trie(filt)
def isBlackList(self, s):
return self.search_trie(s, self.trie)
filt = StringFilter()
filt.addFilter("abc")
filt.addFilter("cbaer")
filt.addFilter("ert")
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))