从 Trie 数据结构中获取单词

Question

我有以下 Trie 数据结构：

public class CDictionary implements IDictionary {

private static final int N = 'z' -'a'+1;

private static class Node {
    private boolean end = false;
    private Node[] next = new Node[N];
}

private int size = 0;
private Node root = new Node();

@Override
public boolean contains(String word) {
    Node node = this.contains(root,word,0);
    if (node == null) {
        return false;
    }
    return node.end;
}

private Node contains(Node node, String str, int d) {
    if (node == null) return null;
    if (d == str.length()) return node;

    char c = str.charAt(d);
    return contains(node.next[c-'a'], str, d+1);
}

@Override
public void insert(String word) {
    this.root = insert(this.root, word, 0);
    this.size++;
}

private Node insert(Node node, String str, int d) {
    if (node == null) node = new Node();
    if (d == str.length()) {
        node.end = true;
        return node;
    }

    char c = str.charAt(d);
    node.next[c-'a'] = this.insert(node.next[c-'a'], str, d+1);
    return node;
}

@Override
public int size() {
    return size;
}

Trie 中充满了一些词，例如

for, the, each, home, is, it, egg, red...

现在我需要一个函数来获取所有具有特定长度的单词，例如长度 3

public List<String> getWords(int lenght) {

}

有了上面提到的单词，它应该 return 一个包含单词

的列表

for,the,egg,red

问题是如何从 Trie 结构中恢复这些单词？

Answer 1

您需要将结构递归到最大深度 N（在本例中为 3）

您可以通过在字典中添加几个方法来做到这一点...

public List<String> findWordsOfLength(int length) {
    // Create new empty list for results
    List<String> results = new ArrayList<>();
    // Start at the root node (level 0)...
    findWordsOfLength(root, "", 0, length, results);
    // Return the results
    return results;
}

public void findWordsOfLength(Node node, String wordSoFar, int depth, int maxDepth, List<String> results) {
    // Go through each "child" of this node
    for(int k = 0; k < node.next.length; k++) {
       Node child = node.next[k];
       // If this child exists...
       if(child != null) {
           // Work out the letter that this child represents
           char letter = 'a' + k;
           // If we have reached "maxDepth" letters...
           if(depth == maxDepth) {
               // Add this letter to the end of the word so far and then add the word to the results list
               results.add(wordSoFar + letter);
           } else {
               // Otherwise recurse to the next level
               findWordsOfLength(child, wordSoDar + letter, depth + 1, maxDepth, results);
           }
       }
    }
}

（我没有编译/测试这个，但它应该让你知道你需要做什么）

希望对您有所帮助。

从 Trie 数据结构中获取单词

Get Words out of a Trie Data Structure

java

search

trie