wildcard on Trie

  • 4

    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:
    //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

    @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.