Getting a list of words from a Trie

Question

I'm looking to use the following code to not check whether there is a word matching in the Trie but to return a list all words beginning with the prefix inputted by the user. Can someone point me in the right direction? I can't get it working at all.....

public boolean search(String s)
{
    Node current = root;
    System.out.println("\nSearching for string: "+s);

    while(current != null)
    {
        for(int i=0;i<s.length();i++)
        {               
            if(current.child[(int)(s.charAt(i)-'a')] == null)
            {
                System.out.println("Cannot find string: "+s);
                return false;
            }
            else
            {
                current = current.child[(int)(s.charAt(i)-'a')];
                System.out.println("Found character: "+ current.content);
            }
        }
        // If we are here, the string exists.
        // But to ensure unwanted substrings are not found:

        if (current.marker == true)
        {
            System.out.println("Found string: "+s);
            return true;
        }
        else
        {
            System.out.println("Cannot find string: "+s +"(only present as a substring)");
            return false;
        }
    }

    return false; 
}

}

Answer 1

After building Trie, you could do DFS starting from node, where you found prefix:

Here Node is Trie node, word=till now found word, res = list of words

def dfs(self, node, word, res):
    # Base condition: when at leaf node, add current word into our list
    if EndofWord at node: 
        res.append(word)
        return
    # For each level, go deep down, but DFS fashion 
    # add current char into our current word.
    for w in node:
        self.dfs(node[w], word + w, res)

Answer 2

The simplest solution is to use a depth-first search.

You go down the trie, matching letter by letter from the input. Then, once you have no more letter to match, everything under that node are strings that you want. Recursively explore that whole subtrie, building the string as you go down to its nodes.