小编zul*_*sam的帖子

我正在实现一个算法来进行目录匹配.所以我给了一组可以包含通配符的有效路径(用"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时,我的算法会沿着突出显示的路径向下停止,因为它之后看不到另一个"朋友",但我怎么能让它将第一个"朋友"识别为通配符值,所以然后它会继续并看到通配符后的第二个"朋友"？

谢谢你的帮助!