添加与搜索单词 - 数据结构设计 · 交互式算法学习

这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。

1class Trie {2    Trie[] children = new Trie[26];3    boolean isEnd;4}5 6class WordDictionary {7    private Trie trie;8 9    /** Initialize your data structure here. */10    public WordDictionary() {11        trie = new Trie();12    }13 14    public void addWord(String word) {15        Trie node = trie;16        for (char c : word.toCharArray()) {17            int idx = c - 'a';18            if (node.children[idx] == null) {19                node.children[idx] = new Trie();20            }21            node = node.children[idx];22        }23        node.isEnd = true;24    }25 26    public boolean search(String word) {27        return search(word, trie);28    }29 30    private boolean search(String word, Trie node) {31        for (int i = 0; i < word.length(); ++i) {32            char c = word.charAt(i);33            int idx = c - 'a';34            if (c != '.' && node.children[idx] == null) {35                return false;36            }37            if (c == '.') {38                for (Trie child : node.children) {39                    if (child != null && search(word.substring(i + 1), child)) {40                        return true;41                    }42                }43                return false;44            }45            node = node.children[idx];46        }47        return node.isEnd;48    }49}50 51/**52 * Your WordDictionary object will be instantiated and called as such:53 * WordDictionary obj = new WordDictionary();54 * obj.addWord(word);55 * boolean param_2 = obj.search(word);56 */