datastructures10Trie

1package pkg3datastructures;2 3/*4 * datastructures10Trie.java  (Prefix Tree)5 * ------------------------6 * Stores strings by shared prefixes. Excellent for autocomplete, spell-check,7 * and prefix queries.8 *9 * COMPLEXITY: insert/search/startsWith O(L) where L = word length.10 * SPACE: up to O(alphabet * nodes); great when many words share prefixes.11 */12import java.util.*;13 14public class datastructures10Trie {15 16    static class TrieNode {17        Map<Character, TrieNode> children = new HashMap<>();18        boolean isWord;19    }20 21    private final TrieNode root = new TrieNode();22 23    void insert(String word) {24        TrieNode node = root;25        for (char c : word.toCharArray())26            node = node.children.computeIfAbsent(c, k -> new TrieNode());27        node.isWord = true;28    }29 30    boolean search(String word) {31        TrieNode node = walk(word);32        return node != null && node.isWord;33    }34 35    boolean startsWith(String prefix) { return walk(prefix) != null; }36 37    private TrieNode walk(String s) {38        TrieNode node = root;39        for (char c : s.toCharArray()) {40            node = node.children.get(c);41            if (node == null) return null;42        }43        return node;44    }45 46    // Collect all words with a given prefix (autocomplete)47    List<String> autocomplete(String prefix) {48        List<String> results = new ArrayList<>();49        TrieNode start = walk(prefix);50        if (start != null) dfs(start, new StringBuilder(prefix), results);51        return results;52    }53 54    private void dfs(TrieNode node, StringBuilder path, List<String> out) {55        if (node.isWord) out.add(path.toString());56        for (Map.Entry<Character, TrieNode> e : node.children.entrySet()) {57            path.append(e.getKey());58            dfs(e.getValue(), path, out);59            path.deleteCharAt(path.length() - 1);60        }61    }62 63    public static void main(String[] args) {64        datastructures10Trie trie = new datastructures10Trie();65        for (String w : new String[]{"cat", "car", "card", "dog", "do", "done"}) trie.insert(w);66 67        System.out.println("search 'car': " + trie.search("car"));68        System.out.println("search 'ca':  " + trie.search("ca"));69        System.out.println("startsWith 'ca': " + trie.startsWith("ca"));70        System.out.println("autocomplete 'ca': " + trie.autocomplete("ca"));71        System.out.println("autocomplete 'do': " + trie.autocomplete("do"));72    }73}