使用通配符值实现Trie

Question

我正在实现一个算法来进行目录匹配.所以我给了一组可以包含通配符的有效路径(用"X"表示).然后当我传入一个输入时,我需要知道该输入是否与我的有效集中的一个路径匹配.当传入的通配符值实际上与另一个有效值匹配时,我遇到了通配符的问题.这是一个例子:

一组有效路径:

/guest
/guest/X
/X/guest
/member
/member/friends
/member/X
/member/X/friends

输入示例:

/member/garbage/friends    
/member/friends/friends

这些应该都返回true,但只有第一个返回true.在第一种情况下,因为"垃圾"与另一个其他可能的路径不匹配,但此时有一个通配符选项,它会跳过它并继续前进,然后它会看到"朋友"并且它知道它是匹配的.但是,我的第二种情况不起作用,因为它看到了朋友,并在我的特里,而不是通配符路径中的不同路径.因为在这个位置有一个有"朋友"的有效路径,所以它认为会是这样.然后它再次看到"朋友",但从trie的这一点来看,没有"朋友"的有效路径,所以它返回false.

我的问题是,我怎样才能让它识别另一个有效的路径,即使它在trie中的错误分支上.我的搜索代码和示例trie图如下.

我的搜索算法如下:

private TrieNode searchNode(String input) {
    Map<String, TrieNode> children = root.children;
    TrieNode t = null;

    // break up input into individual tokens
    String[] tokenizedLine = input.split("/");
    for(int i = 0; i < tokenizedLine.length; i++){
        String current = tokenizedLine[i];

        if(children.containsKey(current)) {
            t = children.get(current);
            children = t.children;
        }else if(children.containsKey("X")){
            t = children.get("X");
            children = t.children;
        }else{
            return null;
        }
    }

    return t;
}

将使用我的样本路径集构建的trie图像: 当我输入/ member/friends/friends时,我的算法会沿着突出显示的路径向下停止,因为它之后看不到另一个"朋友",但我怎么能让它将第一个"朋友"识别为通配符值,所以然后它会继续并看到通配符后的第二个"朋友"？

谢谢你的帮助!

Answer 1

弄清楚了。我实现了一些回溯来跟踪它看到两条可能路径的最后一个节点。如果它在一条路径上发现死胡同，它将返回到上次看到两条可能路径时尝试另一条路径。新算法如下所示：

private TrieNode searchNode(String input) {
        Map<String, TrieNode> children = root.children;
        TrieNode t = null;

        // Variables for backtrack function
        TrieNode alternativeWildcardNode = null;
        int wildcardIndex = 0;
        Map<String, TrieNode> wildcardChildren = root.children;

        // break up input into individual tokens
        String[] tokenizedLine = input.split("/");
        for(int i = 0; i < tokenizedLine.length; i++){
            String current = tokenizedLine[i];

            //System.out.println(current);
            //System.out.println(Integer.toString(i));

            if(children.containsKey(current) && children.containsKey("X")) {
                // store current variable state in case we need to back track here
                alternativeWildcardNode = children.get("X");
                wildcardIndex = i;
                wildcardChildren = alternativeWildcardNode.children;

                t = children.get(current);
                children = t.children;
            }else if(children.containsKey(current)) {
                t = children.get(current);
                children = t.children;
            }else if(children.containsKey("X")){
                t = children.get("X");
                children = t.children;
            }else if(alternativeWildcardNode != null){
                // if we've reached a branch with no match, but had a possible wildcard previously
                // call reset state to the wildcard option instead of static
                t = alternativeWildcardNode;
                alternativeWildcardNode = null;
                i = wildcardIndex;
                children = wildcardChildren;
            }else{
                return null;
            }
        }

        return t;
    }