Get Words out of a Trie Data Structure

Question

i have the following Trie Data Structure:

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;
}

The Trie is filled with some words like

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

Now i need a function to get all Words with a specific length for example the length 3

public List<String> getWords(int lenght) {

}

With the Words mentioned above it should return a list with the words

for,the,egg,red

The Problem is how can i restore these words out of the Trie Structur?

Answer 1

You need to recurse through your structure to a maximum depth of N (in this case 3)

You could do this by adding a couple of methods to your dictionary...

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);
           }
       }
    }
}

(I have not compiled / tested this, but it should give you an idea of what you need to do)

Hope this helps.