实现 Trie (前缀树) · 交互式算法学习

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

1class Trie {2    private Trie[] children;3    private boolean isEnd;4 5    public Trie() {6        children = new Trie[26];7    }8 9    public void insert(String word) {10        Trie node = this;11        for (char c : word.toCharArray()) {12            int idx = c - 'a';13            if (node.children[idx] == null) {14                node.children[idx] = new Trie();15            }16            node = node.children[idx];17        }18        node.isEnd = true;19    }20 21    public boolean search(String word) {22        Trie node = searchPrefix(word);23        return node != null && node.isEnd;24    }25 26    public boolean startsWith(String prefix) {27        Trie node = searchPrefix(prefix);28        return node != null;29    }30 31    private Trie searchPrefix(String s) {32        Trie node = this;33        for (char c : s.toCharArray()) {34            int idx = c - 'a';35            if (node.children[idx] == null) {36                return null;37            }38            node = node.children[idx];39        }40        return node;41    }42}43 44/**45 * Your Trie object will be instantiated and called as such:46 * Trie obj = new Trie();47 * obj.insert(word);48 * boolean param_2 = obj.search(word);49 * boolean param_3 = obj.startsWith(prefix);50 */