wildcard on Trie


  • 4
    Z

    Given such data structure, implement add() and search() method, which support wildcard matching.
    ? Matches any single character.
    * Matches any sequence of characters (including the empty sequence).

    class Node 
    {
    Node getChildForLetter(char letter)
    Node[] getAllChildren();
    boolean isTerminal();
    }
    
    //some example:
    add("car")
    add("caw")
    add("cauw")
    
    search(“c*w”) 
    //should return “caw” and “cauw”.
    // "*" could be at any place in the input string.
    

    This problem is pretty similar to 211. Add and Search Word - Data structure design, but you need to also implement wildcard searching. The brute-force way is not hard to find out, but what about the optimization, any thought on this?


  • 0
    W

    @zzh730 We can add a field at each Trie node, i.e., the maximum length of suffix among all words that share the prefix ending at the current node. When we want to use "*" to match a character represented by a node, we check if the node.maxSuffixLength < inputWord.suffx.length, if so, we can stop searching.


  • 0
    A

    What you can do is to store a dictionary with "wildcard references" for each node.
    currentNode.wildcardReferences['a'] will be a list of first occurrences of letter 'a' in all the subtrees under currentNode. That dictionary will help to identify the possible search paths (since you know which character should be after '*' and you have the corresponding nodes in the dictionary)


Log in to reply
 

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