Problem Statement (Asked By Twitter)

Build an autocomplete system that, given a query string s and a set of possible query strings returns all strings from the set that start with s as a prefix.

Example:

For instance, if the query string is de and the set of strings is ["dog", "deer", "deal"], the output should be ["deer", "deal"].

Hint: Consider preprocessing the set of strings into a more efficient data structure to optimize query performance.

Problem link: https://leetcode.com/problems/design-search-autocomplete-system/description/

Disclaimer: Try solving the problem on your own first! Use this solution only as a reference to learn and improve.

---

Solution:

A simple approach to solve the autocomplete problem is to iterate through a list of words and check if each word starts with the given prefix. If it does, we add it to the result set and return the results.

Naive Solution (Inefficient, O(N)):

import java.util.ArrayList;
import java.util.List;

public class Autocomplete {
    private static final List<String> WORDS = List.of("foo", "bar", "baz", "foobar");

    public static List<String> autocomplete(String prefix) {
        List<String> results = new ArrayList<>();
        for (String word : WORDS) {
            if (word.startsWith(prefix)) {
                results.add(word);
            }
        }
        return results;
    }

    public static void main(String[] args) {
        System.out.println(autocomplete("fo")); // Output: [foo, foobar]
    }
}

While this works, it takes O(N) time to check all words in the list, where N is the number of words.

Optimized Approach Using Trie:

To improve efficiency, we can preprocess the dictionary into a trie. A trie stores each word by splitting it into characters, allowing us to quickly find all words starting with a given prefix.

Trie Implementation in Java:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEndOfWord;

    TrieNode() {
        this.isEndOfWord = false;
    }
}

class Trie {
    private final TrieNode root;

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

    // Insert a word into the trie
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            node.children.putIfAbsent(c, new TrieNode());
            node = node.children.get(c);
        }
        node.isEndOfWord = true;
    }

    // Retrieve all words starting with the given prefix
    public List<String> autocomplete(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            if (!node.children.containsKey(c)) {
                return new ArrayList<>();
            }
            node = node.children.get(c);
        }
        List<String> results = new ArrayList<>();
        collectAllWords(node, prefix, results);
        return results;
    }

    // Helper function to collect all words under a given trie node
    private void collectAllWords(TrieNode node, String prefix, List<String> results) {
        if (node.isEndOfWord) {
            results.add(prefix);
        }
        for (Map.Entry<Character, TrieNode> entry : node.children.entrySet()) {
            collectAllWords(entry.getValue(), prefix + entry.getKey(), results);
        }
    }
}

public class Autocomplete {
    public static void main(String[] args) {
        Trie trie = new Trie();
        String[] words = {"foo", "bar", "baz", "foobar"};
        for (String word : words) {
            trie.insert(word);
        }

        System.out.println(trie.autocomplete("fo")); // Output: [foo, foobar]
        System.out.println(trie.autocomplete("ba")); // Output: [bar, baz]
    }
}

Explanation of Trie Approach:

1. Insertion:
   • Each word is split into characters and stored in a nested map structure (TrieNode).
   • The isEndOfWord flag marks the end of a word.
2. Autocomplete:
   • Navigate through the trie using the prefix characters.
   • Once the prefix node is found, recursively gather all words under that node.
3. Collecting Words:
   • Start from the prefix node and traverse its children to build complete words.

Complexity:

• Insertion: O(L) per word, where L is the length of the word.
• Autocomplete: O(P+W), where P is the length of the prefix and W is the total number of characters in matching words.

This implementation is far more efficient for large dictionaries and frequent prefix searches.

---

Did this solution help you understand the concept better? Let me know your thoughts in the comments below! Don’t forget to follow us on Instagram @coderz.py for more DSA tips and solutions to ace your coding interviews.