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.


Log in to reply
 

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