前缀树（Trie）（字典树）

做leetcode的时候看到前缀树，听都没听过，后来才知道前缀树就是字典树。之前学过，在OJ项目中用字典树来实现黑白名单限制。浅浅复习一下吧

用字典树来实现黑白名单限制 实现步骤

（1）定义黑名单

import java.util.Arrays;
import java.util.List;private static final List<String> blackList = Arrays.asList("Files", "exec");

（2）初始化字典树

 使用 HuTool 的 WordTree 初始化并插入黑名单中的单词。

import cn.hutool.core.text.WordTree;private static final WordTree WORD_TREE;static {// 初始化字典树WORD_TREE = new WordTree();// 插入黑名单中的单词WORD_TREE.addWords(blackList);
}

 （3）校验用户代码

 校验用户输入的代码是否包含黑名单中的禁用词。

// 校验代码中是否包含黑名单中的禁用词
FoundWord foundWord = WORD_TREE.matchWord(code);
if (foundWord != null) {System.out.println("包含禁止词：" + foundWord.getFoundWord());return null; // 或者抛出异常
}

（4）完整代码

import cn.hutool.core.text.WordTree;
import cn.hutool.core.text.WordTree.FoundWord;import java.util.Arrays;
import java.util.List;public class CodeValidator {// 定义黑名单private static final List<String> blackList = Arrays.asList("Files", "exec");// 初始化字典树private static final WordTree WORD_TREE;static {WORD_TREE = new WordTree();WORD_TREE.addWords(blackList);}// 校验用户代码public static String validateCode(String code) {// 校验代码中是否包含黑名单中的禁用词FoundWord foundWord = WORD_TREE.matchWord(code);if (foundWord != null) {System.out.println("包含禁止词：" + foundWord.getFoundWord());return null; // 或者抛出异常}return code; // 如果没有禁用词，返回代码}public static void main(String[] args) {String code = "System.out.println('Hello, World!');";String result = validateCode(code);if (result != null) {System.out.println("代码校验通过！");} else {System.out.println("代码校验失败！");}}
}

深入理解前缀树概念

1 定义

前缀树（Trie）是一种树形数据结构，用于高效地存储和检索字符串集合。它的每个节点表示一个字符，通过节点之间的连接来表示字符串。

2 结构特点

节点（Node）：

1. 每个节点表示一个字符。

2. 每个节点包含一个布尔值 isEnd，表示当前节点是否是一个单词的结尾。

3. 每个节点包含一个数组（或哈希表）next，用于存储其子节点，对应于下一个字符。

根节点（Root Node）：

1. 根节点不存储任何字符，但它是树的起点。
2. 从根节点开始，通过路径上的字符可以拼接出完整的字符串。

3 前缀树的实现

1. Trie 类的定义

class Trie {private boolean isEnd; // 标记是否是单词结尾private Trie[] next;   // 存储子节点的数组public Trie() {isEnd = false; // 初始化时，当前节点不是单词结尾next = new Trie[26]; // 初始化一个大小为26的数组，对应26个小写字母}
}

 2. 插入单词（insert 方法）

public void insert(String word) {Trie node = this; // 从根节点开始for (char c : word.toCharArray()) {int index = c - 'a'; // 计算字符在数组中的索引if (node.next[index] == null) { // 如果当前字符对应的子节点不存在node.next[index] = new Trie(); // 创建一个新的 Trie 节点}node = node.next[index]; // 移动到子节点}node.isEnd = true; // 标记单词结尾
}

3. 搜索单词（search 方法）

public boolean search(String word) {Trie node = this; // 从根节点开始for (char c : word.toCharArray()) {int index = c - 'a'; // 计算字符在数组中的索引node = node.next[index]; // 移动到子节点if (node == null) { // 如果子节点不存在return false; // 单词不存在}}return node.isEnd; // 检查最后一个节点是否是单词结尾
}

4. 搜索前缀（startsWith 方法）

public boolean startsWith(String prefix) {Trie node = this; // 从根节点开始for (char c : prefix.toCharArray()) {int index = c - 'a'; // 计算字符在数组中的索引node = node.next[index]; // 移动到子节点if (node == null) { // 如果子节点不存在return false; // 前缀不存在}}return true; // 前缀存在
}