Trie.java

import java.util.*;

public class Trie {

    private final TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            node.children.putIfAbsent(ch, new TrieNode());
            node = node.children.get(ch);
        }
        node.isEndOfWord = true;
    }

    public List<String> autocomplete(String prefix) {
        TrieNode node = root;

        for (char ch : prefix.toCharArray()) {
            if (!node.children.containsKey(ch)) {
                return Collections.emptyList();
            }
            node = node.children.get(ch);
        }

        List<String> results = new ArrayList<>();
        dfs(node, prefix, results);
        return results;
    }

    private void dfs(TrieNode node, String word, List<String> results) {
        if (node.isEndOfWord) {
            results.add(word);
        }

        for (char ch : node.children.keySet()) {
            dfs(node.children.get(ch), word + ch, results);
        }
    }
}