字符串匹配算法（三）Trie树算法
文章目录
- Trie树的简介
- Trie树定义
- Trie树的实现
- 代码实现
Trie树的简介
Trie树定义
-
Trid树，也叫”字典树“。它是一个树形结构。专门处理字符串匹配的数据结构，用来解决字符串集中快速查找某个字符串的问题。
-
Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。比如：有 6 个字符串，它们分别是：how，hi，her，hello，so，see，我们可以将这六个字符串组成下面的Trie树结构。
-
其中，根节点不包含任何信息。每个节点表示一个字符串中的字符，从根节点到红色节点的一条路径表
示一个字符串（红色节点为叶子节点）
Trie树的实现
- Trie 树是一个多叉树，我们通过一个下标与字符一一映射的数组，来存储子节点的指针。假设我们的字符串中只有从 a 到 z 这 26 个小写字母，我们在数组中下标为 0 的位置，存储指向子节点a 的指针，下标为 1 的位置存储指向子节点 b 的指针，以此类推，下标为 25 的位置，存储的是指向的子节点 z 的指针。如果某个字符的子节点不存在，我们就在对应的下标的位置存储 null。
代码实现
package com.xxliao.algorithms.string_match.trie;/*** @author xxliao* @description: Trie树算法，用于从单词集合中找某个单词* @date 2024/5/31 18:15*/
public class TrieMatch {public static void main(String[] args) {TrieMatch trie=new TrieMatch();trie.insert("hello".toCharArray());trie.insert("her".toCharArray());trie.insert("hi".toCharArray());trie.insert("how".toCharArray());trie.insert("see".toCharArray());trie.insert("so".toCharArray());System.out.println(trie.find("how".toCharArray()));}// 定义根节点字符private TrieNode root = new TrieNode('/');/*** @description 往Trie树中添加字符串* @author xxliao* @date 2024/5/31 18:21*/public void insert(char[] text) {// 定义当前节点TrieNode current = root;for(int i = 0; i < text.length; i++) {//求出字符的索引int index = text[i] -97;if(current.children[index] == null) {TrieNode newNode = new TrieNode(text[i]);current.children[index] = newNode;}current = current.children[index];}current.is_leaf_char = true;}/*** @description 在Trie树中查找字符串* @author xxliao* @date 2024/5/31 18:25*/public boolean find(char[] pattern) {TrieNode current = root;for (int i = 0; i < pattern.length; i++) {int index = pattern[i] - 97;if (current.children[index] == null) {return false; // 不存在pattern}current = current.children[index];}if (current.is_leaf_char == false)return false; // 不能完全匹配，只是前缀return true; // 找到pattern}
}
演示结果：
