Given a query string s and a set of all possible query strings, return all strings in the set that have s as a prefix

Question

Implement an autocomplete system. That is, given a query string s and a set of all possible query strings, return all strings in the set that have s as a prefix.

For example, given the query string de and the set of strings [dog, deer, deal], return [deer, deal].

    class DailyCodingProble11 {

        public static void main(String args[]) {

            String[] words = { "dog", "deer", "deal" };
            Trie trie = new Trie();
            for (String word : words) {
                trie.insert(word);
            }
            trie.search("de", trie.root, 0).stream().forEach(word -> System.out.println(word));
            trie.search("do", trie.root, 0).stream().forEach(word -> System.out.println(word));
        }
    }

        class TrieNode {
            public Character content;
            public TrieNode[] children = new TrieNode[26];
            public boolean isWord;

            TrieNode(Character ch) {
                this.content = ch;
            }
        }

        class Trie {
            TrieNode root;

            Trie() {
                root = new TrieNode('*');
            }

            public void insert(String word) {
                TrieNode currentNode = root;
                for (int i = 0; i < word.length(); i++) {
                    Character ch = word.charAt(i);
                    if (currentNode.children[ch - 'a'] == null) {
                        currentNode.children[ch - 'a'] = new TrieNode(ch);
                    }
                    currentNode = currentNode.children[ch - 'a'];

                }
                currentNode.isWord = true;
            }

            public List<String> search(String searchTxt, TrieNode currentNode, int index) {
                List<String> results = new ArrayList<>();
                Character ch = searchTxt.charAt(index);
                if (currentNode.children[ch - 'a'] == null) {
                    return results;
                }
                currentNode = currentNode.children[ch - 'a'];
                if (index == searchTxt.length() - 1) {
                    findWords(currentNode, new StringBuilder(searchTxt), results);
                    return results;
                }
                return search(searchTxt, currentNode, ++index);
            }

            public void findWords(TrieNode currentNode, StringBuilder sb, List<String> results) {

                for (TrieNode child : currentNode.children) {
                    if (child != null) {
                        if (child.isWord == true) {
                            results.add(sb.append(child.content).toString());
                        }
                        findWords(child, new StringBuilder(sb).append(child.content), results);
                    }
                }
            }


 }

How can I improve my solution? Are there any code improvements?

Answer 1

Hide implementation details of Trie

• root should be private
• current search and findWords methods should be private
• write public version of search: should take only a String and call the private one
• make TrieNode a private static inner class of Trie

Change storage of children

Storing 26 pointers, most of which will be null in regular usage, is wasteful. You should use a more compact data structure; perhaps a TreeMap<Character, TrieNode>. You could even extend TreeMap for a cleaner interface.

Only store characters once

You effectively store each character in two places: explicitly in TrieNode.content, and implicitly by the node's position in its parent's children array (or in the key of the children map if you take my recommendation above). If you grab the character in the previous round of recursion, you should not need the TrieNode.content field at all.

Fix bug using StringBuilder

In findWords if a node is a word and has children, the character will be appended twice.

Minor tweaks

• write a Trie(Iterable<String> content) constructor
• no need to store '*' in root
• use List.forEach() instead of List.stream().forEach()
• separate search functionality into findNode and findWords
• change if (blah == true) to if (blah)
• pass functions instead of using lambdas when possible
• fix indentation -- your IDE should do this for you

Finally, variables names can often be shorter if their purpose is clear in context. For example: currentNode vs current. A lot of people say to "use descriptive variables names"; however, brevity can also help with readability as well.

My stab at the changes

class Trie {
    private static class TrieNode extends TreeMap<Character, TrieNode> {
        public boolean isWord;
    }

    private TrieNode root;

    public Trie(Iterable<String> content) {
        this();
        content.forEach(this::insert);
    }

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

    public void insert(String word) {
        TrieNode current = root;
        for (int i = 0; i < word.length(); i++) {
            current = current.computeIfAbsent(word.charAt(i),
                              k -> new TrieNode());
        }
        current.isWord = true;
    }

    public List<String> search(String word) {
        List<String> results = new ArrayList<>();

        TrieNode node = findNode(word, root, 0);
        if (node == null) {
            return results;
        }

        findWords(node, new StringBuilder(word), results);
        return results;
    }

    private TrieNode findNode(String word, TrieNode current, int index) {
        if (index == word.length()) {
            return current;
        }

        Character ch = word.charAt(index);
        if (!current.containsKey(ch)) {
            return null;
        }

        return findNode(word, current.get(ch), ++index);
    }

    private void findWords(TrieNode current, StringBuilder sb, List<String> results) {
        current.forEach((Character ch, TrieNode child) -> {
            StringBuilder word = new StringBuilder(sb).append(ch);
            if (child.isWord) {
                results.add(word.toString());
            }
            findWords(child, word, results);
        });
    }
}

class TrieTest {
    public static void main(String args[]) {
        Trie trie = new Trie(Arrays.asList(new String[] { "dog", "dee", "deer", "deal" }));

        trie.search("de").forEach(System.out::println);
        System.out.println();

        trie.search("do").forEach(System.out::println);
        System.out.println();
    }
}

Answer 2

Your code does not consider the case when your query string is among the set. You can add that in the search method:

public List<String> search(String word) {
    List<String> results = new ArrayList<>();

    TrieNode node = findNode(word, root, 0);
    if (node == null) {
        return results;
    }
    if(node.isWord) {
        results.add(s);
    }
    findWords(node, new StringBuilder(word), results);
    return results;
}