题目:208.实现 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。示例 1：
输入
["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^4 次思路1
实现 Trie（前缀树）可以通过使用一个嵌套的节点结构。每个节点都包含一个固定大小的数组，用于存储下一个字符的节点指针。具体操作包括插入字符串、查找字符串以及查找前缀。
递归方法:
- TrieNode 定义：每个
TrieNode代表一个节点，它有一个固定大小的数组children来存储26个字母（a-z）的后续节点。此外，节点还需要一个布尔值isEnd来标记当前节点是否为某个完整单词的结束。 - insertDFS 方法：从根节点开始插入字符串的每个字符，如果节点不存在则创建新的节点。
- searchDFS 方法：递归查找字符串的每个字符，查看它是否存在，如果路径中某个节点不存在，则返回
false。如果遍历到最后一个字符找到了对应的前缀或者找到了对应的单词且是单词的结束，返回true，否则继续递归。
- 时间复杂度:O(m)，其中 m 是插入字符串的平均长度。
- 空间复杂度:O(mn)，其中 m 是插入字符串的平均长度, n 是插入字符串的数量。
代码
class Trie {
// 定义Trie节点
private static class TrieNode {
TrieNode[] children;
boolean isEnd;
public TrieNode() {
// 每个节点有26个字母分支
this.children = new TrieNode[26];
// 是否是某个单词的结束
isEnd = false;
}
}
private TrieNode root;
// 初始化前缀树对象
public Trie() {
this.root = new TrieNode();
}
// 向前缀树中插入字符串 word
public void insert(String word) {
insertDFS(root, word, 0);
}
// 如果字符串 word 在前缀树中，返回 true；否则，返回 false
public boolean search(String word) {
return searchDFS(root, word, 0, true);
}
// 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true；否则，返回 false
public boolean startsWith(String prefix) {
return searchDFS(root, prefix, 0, false);
}
private void insertDFS(TrieNode node, String word, int index) {
if (index == word.length()) {
return;
}
char c = word.charAt(index);
if (node.children[c - 'a'] == null) {
// 创建新的节点
node.children[c - 'a'] = new TrieNode();
}
node = node.children[c - 'a'];
if (index == word.length() - 1) {
// 插入完毕，标记为单词的结束
node.isEnd = true;
return;
}
insertDFS(node, word, index + 1);
}
private boolean searchDFS(TrieNode node, String word, int index, boolean matchAll) {
if (index == word.length()) {
return false;
}
char c = word.charAt(index);
if (node.children[c - 'a'] == null) {
// 如果路径中某个节点不存在，则返回 false
return false;
}
node = node.children[c - 'a'];
// 如果找到了对应的前缀或者找到了对应的单词且是单词的结束，返回 true
if (index == word.length() - 1 && (!matchAll || node.isEnd)) {
return true;
}
return searchDFS(node, word, index + 1, matchAll);
}
}思路2
实现 Trie（前缀树）可以通过使用一个嵌套的节点结构。每个节点都包含一个固定大小的数组，用于存储下一个字符的节点指针。具体操作包括插入字符串、查找字符串以及查找前缀。
迭代方法:
- TrieNode 定义：每个
TrieNode代表一个节点，它有一个固定大小的数组children来存储26个字母（a-z）的后续节点。此外，节点还需要一个布尔值isEnd来标记当前节点是否为某个完整单词的结束。 - insertHelper 方法：从根节点开始插入字符串的每个字符，如果节点不存在则创建新的节点。
- searchHelper 方法：遍历字符串的每个字符，查看它是否存在，如果路径中某个节点不存在，则返回
false。如果遍历到最后一个字符找到了对应的前缀或者找到了对应的单词且是单词的结束，返回true，否则返回false。
- 时间复杂度:O(m)，其中 m 是插入字符串的平均长度。
- 空间复杂度:O(mn)，其中 m 是插入字符串的平均长度, n 是插入字符串的数量。
代码
class Trie {
// 定义Trie节点
private static class TrieNode {
TrieNode[] children;
boolean isEnd;
public TrieNode() {
// 每个节点有26个字母分支
this.children = new TrieNode[26];
// 是否是某个单词的结束
isEnd = false;
}
}
private TrieNode root;
// 初始化前缀树对象
public Trie() {
this.root = new TrieNode();
}
// 向前缀树中插入字符串 word
public void insert(String word) {
insertHelper(root, word);
}
// 如果字符串 word 在前缀树中，返回 true；否则，返回 false
public boolean search(String word) {
return searchHelper(root, word, true);
}
// 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true；否则，返回 false
public boolean startsWith(String prefix) {
return searchHelper(root, prefix, false);
}
private void insertHelper(TrieNode node, String word) {
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (node.children[c - 'a'] == null) {
// 创建新的节点
node.children[c - 'a'] = new TrieNode();
}
node = node.children[c - 'a'];
}
// 插入完毕，标记为单词的结束
node.isEnd = true;
}
private boolean searchHelper(TrieNode node, String word, boolean matchAll) {
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (node.children[c - 'a'] == null) {
// 如果路径中某个节点不存在，则返回 false
return false;
}
node = node.children[c - 'a'];
}
// 如果找到了对应的前缀或者找到了对应的单词且是单词的结束，返回 true
return !matchAll || node.isEnd;
}
}
