实现 Trie (前缀树)

难度:

标签:

题目描述

Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：

输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True

提示：

1 <= word.length, prefix.length <= 2000
word 和 prefix 仅由小写英文字母组成
insert、search 和 startsWith 调用次数总计不超过 3 * 10⁴ 次

代码结果

运行时间: 78 ms, 内存: 27.8 MB

// Trie class implementation in Java using Java Streams
 
// This is a Trie data structure which is used to efficiently store and retrieve keys in a dataset of strings.
// Each node in the Trie represents a single character of a word.
 
import java.util.HashMap;
import java.util.Map;
 
class TrieNode {
    public Map<Character, TrieNode> children = new HashMap<>();
    public boolean isEndOfWord = false;
}
 
public class Trie {
    private final TrieNode root;
 
    // Constructor to initialize the root of the Trie
    public Trie() {
        root = new TrieNode();
    }
 
    // Inserts a word into the trie.
    public void insert(String word) {
        TrieNode node = root;
        word.chars().mapToObj(c -> (char) c).forEach(c -> {
            node.children.putIfAbsent(c, new TrieNode());
            node = node.children.get(c);
        });
        node.isEndOfWord = true;
    }
 
    // Returns if the word is in the trie.
    public boolean search(String word) {
        TrieNode node = root;
        return word.chars().mapToObj(c -> (char) c).allMatch(c -> {
            if (node.children.get(c) == null) {
                return false;
            }
            node = node.children.get(c);
            return true;
        }) && node.isEndOfWord;
    }
 
    // Returns if there is any word in the trie that starts with the given prefix.
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        return prefix.chars().mapToObj(c -> (char) c).allMatch(c -> {
            if (node.children.get(c) == null) {
                return false;
            }
            node = node.children.get(c);
            return true;
        });
    }
}

解释

方法:

这个题解使用 Trie（字典树）数据结构来实现字符串的快速插入、查询和前缀匹配。Trie 中的每个节点表示一个字符，从根节点到某一节点的路径表示该节点对应的字符串。在插入字符串时，从根节点出发，沿着字符串的字符遍历 Trie，如果对应的子节点不存在，则创建一个新的子节点。查询时，同样沿着字符串的字符遍历 Trie，如果某个字符对应的子节点不存在，则说明 Trie 中不包含该字符串。如果遍历到最后一个字符的节点，且该节点是一个词的末尾（可用一个特殊字符 '#' 表示），则说明 Trie 中存在该字符串。前缀匹配时，只需判断能否在 Trie 中找到前缀对应的路径即可。

时间复杂度:

O(m)，其中 m 为字符串的长度

空间复杂度:

O(n * k)，其中 n 为字符串的平均长度，k 为字符串的数量

代码细节讲解

🦆

在`Trie`类的初始化中，你使用了一个字典来表示根节点。请问在实际情况中，使用字典存储节点与使用固定大小数组存储节点相比，有哪些优缺点？

▷

使用字典存储 Trie 节点的优点包括灵活性和空间效率。字典允许动态地添加和查找字符，不需要预先定义数组的大小，适用于字符种类多样的情况。此外，字典只存储实际存在的字符，可以节省空间。然而，字典的缺点是相较于数组，其查找和插入操作可能较慢，因为字典的内部实现复杂度高于简单的数组索引。使用固定大小数组的优点是访问速度快，因为可以直接通过字符的 ASCII 值计算索引，操作时间复杂度为 O(1)。缺点是可能会浪费空间，特别是当字符集很大时，许多数组元素可能为空，尤其是在存储稀疏数据时。

🦆

你提到在插入单词的末尾节点处加入一个特殊字符`#`来标识单词的结束。请问这种方法与在节点中使用一个布尔标志`isEnd`来标识结束有什么不同？哪一种方法更优？

▷

使用特殊字符`#`来标识单词的结束和使用布尔标志`isEnd`的主要区别在于实现方式。使用`#`字符的方法需要在字典中添加一个特殊的键，其值通常为自身或者一个标记值，这种方法使得结束标记与其他字符的存储方式一致，便于统一处理。而使用布尔标志`isEnd`则需要在每个节点中额外存储一个布尔值，此方法直观且容易理解。从性能角度看，布尔标志`isEnd`可能更优，因为它不需要为结束标志单独存储额外的键值对，节省了空间。此外，布尔值的检查通常比字典键的检查要快。

🦆

在`search`函数中，你检查了`#`字符是否存在于最后一个字符的子节点字典中。如果存在其他方法判断一个字符串是否被完整存储在Trie中，这些方法可能是什么？

▷

除了使用`#`字符标记之外，其他方法可包括：1. 使用已提及的布尔标志`isEnd`，在每个节点中设置一个布尔值来直接标识该节点是否代表一个单词的结束。这种方法可以直接判断最后一个字符的节点的`isEnd`值，如果为真，则表示字符串完整存储在 Trie 中。2. 在节点中维护一个计数器或列表，记录该节点作为单词结尾的次数或具体单词，这适用于需要统计单词出现次数或记录多个单词共用节点的场景。这些方法各有优劣，实际使用中可根据具体需求和性能考量选择适合的方法。

相关问题

添加与搜索单词 - 数据结构设计

请你设计一个数据结构，支持添加新单词和查找字符串是否与任何先前添加的字符串匹配。

实现词典类 WordDictionary ：

WordDictionary() 初始化词典对象
void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回 false 。word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。

示例：

输入：
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
输出：
[null,null,null,null,false,true,true,true]

解释：
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // 返回 False
wordDictionary.search("bad"); // 返回 True
wordDictionary.search(".ad"); // 返回 True
wordDictionary.search("b.."); // 返回 True

提示：

1 <= word.length <= 25
addWord 中的 word 由小写英文字母组成
search 中的 word 由 '.' 或小写英文字母组成
最多调用 10⁴ 次 addWord 和 search

设计搜索自动补全系统

单词替换

在英语中，我们有一个叫做 词根(root) 的概念，可以词根后面添加其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。

现在，给定一个由许多词根组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。

你需要输出替换之后的句子。

示例 1：

输入：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
输出："the cat was rat by the bat"

示例 2：

输入：dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
输出："a a b c"

提示：

1 <= dictionary.length <= 1000
1 <= dictionary[i].length <= 100
dictionary[i] 仅由小写字母组成。
1 <= sentence.length <= 10^6
sentence 仅由小写字母和空格组成。
sentence 中单词的总量在范围 [1, 1000] 内。
sentence 中每个单词的长度在范围 [1, 1000] 内。
sentence 中单词之间由一个空格隔开。
sentence 没有前导或尾随空格。

实现一个魔法字典

设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。

实现 MagicDictionary 类：

MagicDictionary() 初始化对象
void buildDict(String[] dictionary) 使用字符串数组 dictionary 设定该数据结构，dictionary 中的字符串互不相同
bool search(String searchWord) 给定一个字符串 searchWord ，判定能否只将字符串中一个字母换成另一个字母，使得所形成的新字符串能够与字典中的任一字符串匹配。如果可以，返回 true ；否则，返回 false 。

示例：

输入
["MagicDictionary", "buildDict", "search", "search", "search", "search"]
[[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
输出
[null, null, false, true, false, false]

解释
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict(["hello", "leetcode"]);
magicDictionary.search("hello"); // 返回 False
magicDictionary.search("hhllo"); // 将第二个 'h' 替换为 'e' 可以匹配 "hello" ，所以返回 True
magicDictionary.search("hell"); // 返回 False
magicDictionary.search("leetcoded"); // 返回 False

提示：

1 <= dictionary.length <= 100
1 <= dictionary[i].length <= 100
dictionary[i] 仅由小写英文字母组成
dictionary 中的所有字符串 互不相同
1 <= searchWord.length <= 100
searchWord 仅由小写英文字母组成
buildDict 仅在 search 之前调用一次
最多调用 100 次 search

课程表长度最小的子数组