Implement Trie (Prefix Tree)

1package pkg5leetcode.blind75;2 3/*4 * Implement Trie (Prefix Tree) | LC 2085 * APPROACH: 26-child nodes per level; mark word ends.6 * COMPLEXITY: Time O(m) per op, Space O(total chars)7 */8public class blind75_LC208ImplementTrie {9    static class Trie {10        Trie[] child = new Trie[26];11        boolean end;12 13        Trie() {}14 15        void insert(String word) {16            Trie node = this;17            for (char c : word.toCharArray()) {18                int i = c - 'a';19                if (node.child[i] == null) node.child[i] = new Trie();20                node = node.child[i];21            }22            node.end = true;23        }24 25        boolean search(String word) {26            Trie node = find(word);27            return node != null && node.end;28        }29 30        boolean startsWith(String prefix) {31            return find(prefix) != null;32        }33 34        Trie find(String s) {35            Trie node = this;36            for (char c : s.toCharArray()) {37                int i = c - 'a';38                if (node.child[i] == null) return null;39                node = node.child[i];40            }41            return node;42        }43    }44 45    public static void main(String[] args) {46        Trie trie = new Trie();47        trie.insert("apple");48        check(trie.search("apple"), "case1");49        check(!trie.search("app"), "case2");50        check(trie.startsWith("app"), "prefix");51        System.out.println("all tests passed");52    }53 54    static void check(boolean cond, String name) {55        if (!cond) throw new AssertionError("FAILED: " + name);56        System.out.println("  PASS " + name);57    }58}