how to solve this problem using trie? thanks


  • 0
    O

    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.


  • 0
    M

    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))


  • 1
    E

    Should be doable in O(n^2)


Log in to reply
 

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