4 |
您所在的位置：网站首页 › 前缀树leetcode › 4 |
4
|
1. 题目
https://leetcode.cn/problems/implement-trie-prefix-tree/ 2. 解法什么是 Trie (前缀树)？ Trie (前缀树) 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。 它的每个节点都包含一个长度为 26 的数组，用来存储它的子节点，数组的下标对应字符的顺序。 它的每个节点还包含一个布尔值，用来表示它是否是单词的结尾。 前缀树为什么叫trie 前缀树为什么叫trie，是因为它的英文名字trie是retrieval（检索）的中间部分，由Edward Fredkin在1960年提出的1。trie的发音有两种，一种是和tree一样，另一种是和try一样2。trie这个名字反映了它的结构使它成为一个优秀的匹配算法。 Trie 的优缺点 Trie 的优点是可以快速地找到以指定字符串为前缀的所有单词，或者判断一个字符串是否存在于数据集中。 Trie 的缺点是需要占用较多的空间，因为每个节点都需要存储一个数组。 Trie 的应用场景 Trie 的应用场景有很多，比如自动补全和拼写检查。 例如，当你在 Google 搜索框中输入一个字符串时，它会根据你输入的内容给出一些可能的搜索建议，这就是利用了 Trie 的特性。 Trie 的扩展知识Trie 的应用场景有很多，比如自动补全和拼写检查。除了基本的插入、搜索和前缀匹配，Trie 还有一些其他的应用和变种，下面介绍一些常见的例子： 压缩 Trie：为了节省空间，压缩 Trie 将没有分叉的节点合并成一个节点，只存储该节点的起始字符和结束字符。这样可以减少节点的数量，提高空间利用率。 后缀 Trie：后缀 Trie 是一种特殊的 Trie，它存储了一个字符串的所有后缀。这样可以方便地判断一个字符串是否是另一个字符串的子串或后缀，或者找到两个字符串的最长公共后缀。 后缀树：后缀树是一种压缩后缀 Trie，它将没有分叉的节点合并成一个节点，并且在每个节点上存储该节点对应的子串在原字符串中的位置。这样可以进一步节省空间，并且提高查询效率。后缀树可以用来解决很多字符串相关的问题，比如最长重复子串、最长公共子串等。 字典树：字典树是一种用来存储词典或者词汇表的 Trie，它可以用来实现自动补全和拼写检查等功能。字典树通常会在每个节点上存储一些额外的信息，比如单词的频率、意义、同义词等。这样可以增加单词的语义信息，并且提高用户体验。 二进制 Trie：二进制 Trie 是一种用来存储二进制数的 Trie，它只有两个子节点，分别表示 0 和 1。二进制 Trie 可以用来实现 IP 路由表等功能。它可以快速地找到与给定二进制数最接近或最远的数，或者找到两个二进制数的异或值。 如何实现 Trie (前缀树)？ 要实现 Trie (前缀树)，我们需要定义一个 Trie 类，以及一个内部类 TrieNode，表示 Trie 中的每个节点。 我们还需要实现三个方法：insert、search 和 startsWith，分别用来向 Trie 中插入一个字符串、搜索 Trie 中是否有指定的字符串、检查 Trie 中是否有以指定字符串为前缀的单词。实现思路 解题思路是这样的： 首先，我定义了一个内部类 TrieNode，表示 Trie 中的每个节点。每个节点有一个长度为 26 的数组，用来存储它的子节点，数组的下标对应字符的顺序。每个节点还有一个布尔值，用来表示它是否是单词的结尾。 然后，我定义了一个根节点，用来表示 Trie 的起点。在初始化 Trie 对象时，我将根节点设为一个新的 TrieNode 对象。 接着，我实现了 insert 方法，用来向 Trie 中插入一个字符串。我从根节点开始遍历字符串中的每个字符，根据字符的顺序找到对应的子节点。如果子节点不存在，就创建一个新的 TrieNode 对象并插入到数组中。最后，我将最后一个字符对应的节点的布尔值设为 true，表示这是一个单词的结尾。 然后，我实现了 search 方法，用来在 Trie 中搜索一个字符串。我从根节点开始遍历字符串中的每个字符，根据字符的顺序找到对应的子节点。如果子节点不存在，就说明 Trie 中没有这个字符串，返回 false。最后，我返回最后一个字符对应的节点的布尔值，如果是 true，说明 Trie 中有这个字符串，否则返回 false。 最后，我实现了 startsWith 方法，用来检查 Trie 中是否有以指定字符串为前缀的单词。我从根节点开始遍历字符串中的每个字符，根据字符的顺序找到对应的子节点。如果子节点不存在，就说明 Trie 中没有以这个字符串为前缀的单词，返回 false。最后，我返回 true，说明 Trie 中有以这个字符串为前缀的单词。具体实现 public class Trie { class TrieNode { TrieNode[] children; boolean isEnd; public TrieNode() { children = new TrieNode[26]; isEnd = false; } } private TrieNode root; public Trie() { root = new TrieNode(); } public void insert(String word) { TrieNode node = root; for (int i = 0; i < word.length(); i++) { int index = word.charAt(i) - 'a'; if (node.children[index] == null) { node.children[index] = new TrieNode(); } node = node.children[index]; } node.isEnd = true; } public boolean search(String word) { TrieNode node = root; for (int i = 0; i < word.length(); i++) { int index = word.charAt(i) - 'a'; if (node.children[index] == null) { return false; } node = node.children[index]; } return node.isEnd; } public boolean startWith(String prefix) { TrieNode node = root; for (int i = 0; i < prefix.length(); i++) { int index = prefix.charAt(i) - 'a'; if (node.children[index] == null) { return false; } node = node.children[index]; } return true; } }
3. 总结 |
【本文地址】
今日新闻 |
推荐新闻 |