Trie implementation in Java

Question

This is my implementation of a Trie.

public class Trie {

    private class Node{
        private Map<Character, Node> children;
        boolean end;

        public Node(){
            children = new HashMap<>();
            end = false;
        }
    }

    private Node root;

    public Trie(){
        root = new Node();
    }

    public void insert(String word){
        Node current = root;
        for (int i=0; i < word.length(); i++){
            char c = word.charAt(i);
            Node node = current.children.get(c);
            if(node == null){
                node = new Node();
                current.children.put(c, node);
            }
            current = node;
        }
    }

    public boolean search(String word){
        Node current = root;
        for(int i =0; i < word.length(); i++){
            char c = word.charAt(i);
            Node node = current.children.get(c);
            if(node == null) 
                return false;
            current = node;
        }
        return current.end;
    }
}

I want to add a method, that given a string return all its children, something that could be used as a real world autocorrect suggestions.

Here's the method signature:

public List<String> returnAllChildren(String str){

}

I'm a little lost with this one. Any help appreciated.

Iteration is fine when you want to go down just one child of each node. But for your problem, you want to go down all of the children of each node. "SImple" iteration isn't good enough for that. (You can do it without recursion by keeping a "to-do" list of nodes that you haven't examined yet. But I think the recursive solution is a little simpler.) — ajb
– ajb, Commented Mar 25, 2017 at 3:42

Ke Li · Accepted Answer · 2017-03-25 04:16:55Z

First of all, when you insert a node, you should set end=true at the tail node. And then when lookup a prefix in Trie, you only need to find the node of last character in prefix and then get all strings recursively. Here is a example maybe could help you:

public class Trie {

private class Node{
    private Map<Character, Node> children;
    boolean end;

    public Node(){
        children = new HashMap<>();
        end = false;
    }
}

private Node root;

public Trie(){
    root = new Node();
}

public void insert(String word){
    Node current = root;
    for (int i=0; i < word.length(); i++){
        char c = word.charAt(i);
        Node node = current.children.get(c);
        if(node == null){
            node = new Node();
            current.children.put(c, node);
        }
        current = node;
    }
    // Set end to true
    current.end = true;
}

public boolean search(String word){
    Node current = root;
    for(int i =0; i < word.length(); i++){
        char c = word.charAt(i);
        Node node = current.children.get(c);
        if(node == null)
            return false;
        current = node;
    }
    return current.end;
}


private List<String> getAll(String prefix, Node node) {
    List<String> r = new ArrayList<>();
    if (node.end) {
        r.add(prefix);
    }
    for (Map.Entry<Character, Node> child : node.children.entrySet()) {
        List<String> subSuffix = getAll(prefix + child.getKey(), child.getValue());
        r.addAll(subSuffix);
    }
    return r;
}

public List<String> returnAllChildren(String str){
    List<String> r = new ArrayList<>();
    Node current = root;
    for (int i = 0; i < str.length(); i++) {
        char c = str.charAt(i);
        Node node = current.children.get(c);
        if (node == null) {
            // Not found
            return r;
        }
        current = node;
    }
    // If you don't need the prefix, you can just
    // return getAll("", current);
    return getAll(str, current);
}

public static void main(String[] args) {
    Trie trie = new Trie();
    trie.insert("abc");
    trie.insert("abcd");
    trie.insert("ab");

    List<String> r = trie.returnAllChildren("a");
    for (String s : r) {
        System.out.println(s);
    }
}
}

Collectives™ on Stack Overflow

Trie implementation in Java

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related