算法-字典树

模板

class TrieNode {
    boolean isEnd; // 是否为单词末尾
    TrieNode[] next; // 孩子节点数组
    public TrieNode() {
        this.isEnd = false;
        this.next = new TrieNode[26];
    }
}

class Trie {
    TrieNode root; // 虚拟头节点

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) { // 插入单词
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            // 先判断是否有该分支，再跳转
            if (node.next[c - 'a'] == null) {
                node.next[c - 'a'] = new TrieNode();
            }
            node = node.next[c - 'a'];
        }
        node.isEnd = true; // 标记
    }

    public boolean search(String word) { // 搜索单词
        TrieNode node = root;
        // 判断每个字符是否都存在
        for (char c : word.toCharArray()) {
            node = node.next[c - 'a'];
            if (node == null) {
                return false;
            }
        }
        // 判断末尾
        return node.isEnd;
    }

    public boolean startsWith(String prefix) { // 判断前缀
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            node = node.next[c - 'a'];
            if (node == null) {
                return false;
            }
        }
        // 走到这里就说明是前缀！！
        return true;
    }
}

@#参考

作者：wxyz
链接：https://leetcode.cn/problems/minimum-number-of-valid-strings-to-form-target-i/solutions/3022452/trie-yuan-li-tui-dao-mo-ban-tu-jie-zi-di-w1sz/