题目
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 <= 2000word和prefix仅由小写英文字母组成insert、search和startsWith调用次数 总计 不超过 3 * 104 次
思路
- 题目要求实现一个Trie，包含插入、查找和查找前缀三个方法。
- Trie树也称字典树，因为其效率很高，所以在在字符串查找、前缀匹配等中应用很广泛，其高效率是以空间为代价的。
- 原理：利用串构建一个字典树，这个字典树保存了串的公共前缀信息，因此可以降低查询操作的复杂度。
- 定义结点Node里包含一个ch(存储字符)、isEnd(表示这个结点是否是一个词的结尾)和一个next(存储下一个字符结点)。
定义一个根结点root作为整棵树的查找起点。
比如插入一个词"中国制造"：
我们从root开始，依次往下查找'中','国','制','造'：如果在结点n的下一个字符列表里没有找到我们想要的字符ch，我们就增加新结点到结点n的next。
查找一个词"中国制造"：
我们从root开始，依次往下查找'中','国','制','造'：如果在结点n的下一个字符列表里没有找到我们想要的字母ch，那么说明不存在，返回false;如果有，那么继续往下找，直到查找的词"中国制造"找到最后一位，这时候我们判断一下这个位置的isWord是否为true，如果为true说明这是一个完整单词，否则只是部分，返回False。
查找一个前缀
查找一个前缀和查找一个单词的区别就是，当我们想要查找的前缀找到最后一位，不需要判断是否是完整的单词，直接返回true即可。如果不能全部找到则返回False。
复杂度
- 空间复杂度: 字典树每个节点都需要用一个列表存储下一个字符结点，所以空间复杂度较高。
- 时间复杂度: 假设所有插入字符串长度之和为n，构建字典树的时间复杂度为O(n)；假设要查找的所有字符串长度之和为k，查找的时间复杂度为O(k)。因此时间复杂度为O(n+k)
代码
下面代码列出了insert、search、startswith、delete四种操作，题目中只要求insert、search、startsWith。
import java.util.LinkedList;
import java.util.List;
public class Trie {
static class Node {
public char ch;
public boolean isEnd;
public List<Node> next;
public Node(char ch) {
this.ch = ch;
this.isEnd = false;
this.next = new LinkedList<>();
}
public Node findNode(char ch) {
for (Node node : next) {
if (node.ch == ch) {
return node;
}
}
return null;
}
}
private Node root;
public Trie() {
root = new Node('\0');
}
public void insert(String word) {
Node current = root;
int n = word.length();
for (int i = 0; i < n; i++) {
char ch = word.charAt(i);
Node node = current.findNode(ch);
if (node == null) {
node = new Node(ch);
current.next.add(node);
}
current = node;
}
current.isEnd = true;
}
public boolean search(String word) {
Node current = root;
int n = word.length();
for (int i = 0; i < n; i++) {
char ch = word.charAt(i);
Node node = current.findNode(ch);
if (node == null) {
return false;
}
else {
current = node;
}
}
return current.isEnd;
}
public boolean startWith(String prefix) {
Node current = root;
int n = prefix.length();
for (int i = 0; i < n; i++) {
char ch = prefix.charAt(i);
Node node = current.findNode(ch);
if (node == null) {
return false;
}
else {
current = node;
}
}
return true;
}
public boolean delete(String word) {
Node current = root;
int n = word.length();
List<Node> path = new LinkedList<>();
for (int i = 0; i < n; i++) {
char ch = word.charAt(i);
Node node = current.findNode(ch);
if (node == null) {
return false;
}
else {
path.add(node);
current = node;
}
}
boolean isDelete = false;
Node child = null;
for (int i = path.size() - 1; i >= 0; i--) {
Node node = path.get(i);
if (isDelete) {
node.next.remove(child);
}
if (node.next.isEmpty() && node.isEnd) {
isDelete = true;
child = node;
}
}
return true;
}
}Demo
public class TrieTreeDemo {
public static void main(String[] args) {
Trie tree = new Trie();
tree.insert("北京");
tree.insert("海淀区");
tree.insert("中国");
tree.insert("中国人民");
tree.insert("中国制造");
tree.insert("中关村");
String word = "中国";
//查找该词是否存在 Trid Tree 中
boolean flag = tree.search(word);
if (flag) {
System.out.println("Trie Tree 中已经存在【" + word + "】");
} else {
System.out.println("Trie Tree 不包含【" + word + "】");
}
word = "中国人民";
//查找该词是否存在 Trid Tree 中
flag = tree.search(word);
if (flag) {
System.out.println("Trie Tree 中已经存在【" + word + "】");
} else {
System.out.println("Trie Tree 不包含【" + word + "】");
}
String prefix = "中关";
flag = tree.startWith(prefix);
if (flag) {
System.out.println("Trie Tree 中已经存在【" + prefix + "】");
} else {
System.out.println("Trie Tree 不包含【" + prefix + "】");
}
word = "中国人民";
//查找该词是否存在 Trid Tree 中
flag = tree.delete(word);
//查找该词是否存在 Trid Tree 中
flag = tree.search(word);
if (flag) {
System.out.println("Trie Tree 中已经存在【" + word + "】");
} else {
System.out.println("Trie Tree 不包含【" + word + "】");
}
word = "中国";
//查找该词是否存在 Trid Tree 中
flag = tree.search(word);
if (flag) {
System.out.println("Trie Tree 中已经存在【" + word + "】");
} else {
System.out.println("Trie Tree 不包含【" + word + "】");
}
word = "中国制造";
//查找该词是否存在 Trid Tree 中
flag = tree.search(word);
if (flag) {
System.out.println("Trie Tree 中已经存在【" + word + "】");
} else {
System.out.println("Trie Tree 不包含【" + word + "】");
}
}
}
