Implement Trie (Prefix Tree)

1package pkg5leetcode.official75;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 official75_LC208ImplementTrie {9    static class Trie {10        Trie[] child = new Trie[26];11        boolean end;12 13        void insert(String word) {14            Trie node = this;15            for (char c : word.toCharArray()) {16                int i = c - 'a';17                if (node.child[i] == null) node.child[i] = new Trie();18                node = node.child[i];19            }20            node.end = true;21        }22 23        boolean search(String word) {24            Trie node = find(word);25            return node != null && node.end;26        }27 28        boolean startsWith(String prefix) {29            return find(prefix) != null;30        }31 32        Trie find(String s) {33            Trie node = this;34            for (char c : s.toCharArray()) {35                int i = c - 'a';36                if (node.child[i] == null) return null;37                node = node.child[i];38            }39            return node;40        }41    }42 43    public static void main(String[] args) {44        Trie trie = new Trie();45        trie.insert("apple");46        check(trie.search("apple"), "case1");47        check(!trie.search("app"), "case2");48        check(trie.startsWith("app"), "prefix");49        System.out.println("all tests passed");50    }51 52    static void check(boolean cond, String name) {53        if (!cond) throw new AssertionError("FAILED: " + name);54        System.out.println("  PASS " + name);55    }56}