java - DFS over string trie (前缀)

Question

我写了以下前缀树:

class TrieNode {
    char letter;
    HashMap<Character,TrieNode> children;
    boolean fullWord;

    TrieNode(char letter) {
        this.letter = letter;
        children = new  HashMap<Character, TrieNode>();
        this.fullWord = false;
    }
}

class Tree{
    static TrieNode createTree() {
         return (new TrieNode('\0'));
    }

    static void insertWord(TrieNode root, String word) {
        int l = word.length();
        char[] letters = word.toCharArray();
        TrieNode curNode = root;
        for (int i = 0; i < l; i++) {
            if (!curNode.children.containsKey(letters[i]))
                curNode.children.put(letters[i], new TrieNode(letters[i]));
            curNode = curNode.children.get(letters[i]);
        }
        curNode.fullWord = true;
    }
}

我想添加 DFS 方法以找到第一个有多个子节点的节点(因此它会显示最长的公共(public)前缀)。

我写了这段代码:

static void DFS(TrieNode node) {
    for (TrieNode tn: node.children.values()){
       DFS(tn);
        if (node.children.size()>2)
        System.out.println("found the first vertex");
    }
}

但它不起作用。我做错了什么？

Answer 1

那么，首先我们需要明确的是，这里的longest common prefix是指trie树中任意两个或多个字符串的最长公共(public)前缀。

因此，您的 DFS 方法将无法正常工作，因为它只是遍历整棵树，并在访问任何 children.size() > 2 (< em>这里应该>=2)

我们在这里想要的只是找到最长 公共(public)前缀。所以我们需要一些关于哪个最长的额外信息。在我上面的例子中很容易看出:

          root      --depth: 0
           |
           a        --depth: 1
           |
           b        --depth: 2
          / \
         c   f      --depth: 3
        /|\
       d g k        --depth: 4
            \
             k      --depth: 5 

最长的公共(public)前缀节点有 children.size()>1 AND 有最大深度。在本例中，它是节点 c

所以这是一个可能正确的 DFS:

static int max=-1;
static TrieNode maxNode=null;

static void dfs(TrieNode node, int depth){
    if(node.children.size()>1 && depth>max){
        max=depth;
        maxNode=node;
    }
    for (TrieNode tn: node.children.values())
        dfs(tn,depth+1);
}

public static void test(){
    TrieNode root = Tree.createTree();
    Tree.insertWord(root, "abcd");
    Tree.insertWord(root, "abcg");
    Tree.insertWord(root, "abckk");
    Tree.insertWord(root, "abf");
    dfs(root,0);
    System.out.println("Max node:"+maxNode.letter);
}

运行 dfs 后，ma​​xNode 将保存最长公共(public)前缀停止的节点。在这种情况下是节点 c。