Design Add and Search Words Data Structure

1package pkg5leetcode.blind75;2 3/*4 * Design Add and Search Words Data Structure | LC 2115 * APPROACH: Trie insert; DFS search with '.' wildcard branches.6 * COMPLEXITY: Time O(m) insert, O(26^d) search worst case7 */8public class blind75_LC211DesignAddAndSearchWordsDataStructure {9    static class WordDictionary {10        static class Node {11            Node[] child = new Node[26];12            boolean end;13        }14 15        Node root = new Node();16 17        void addWord(String word) {18            Node node = root;19            for (char c : word.toCharArray()) {20                int i = c - 'a';21                if (node.child[i] == null) node.child[i] = new Node();22                node = node.child[i];23            }24            node.end = true;25        }26 27        boolean search(String word) {28            return dfs(root, word, 0);29        }30 31        boolean dfs(Node node, String word, int idx) {32            if (node == null) return false;33            if (idx == word.length()) return node.end;34            char c = word.charAt(idx);35            if (c == '.') {36                for (Node ch : node.child) if (dfs(ch, word, idx + 1)) return true;37                return false;38            }39            return dfs(node.child[c - 'a'], word, idx + 1);40        }41    }42 43    public static void main(String[] args) {44        WordDictionary wd = new WordDictionary();45        wd.addWord("bad");46        wd.addWord("dad");47        wd.addWord("mad");48        check(!wd.search("pad"), "case1");49        check(wd.search("bad"), "case2");50        check(wd.search(".ad"), "wildcard");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}