Trie
Trie,又称前缀树或字典树,用于判断字符串是否存在或者是否具有某种字符串前缀。Trie字典树主要用于存储字符串,Trie 的每个 Node 保存一个字符。用链表来描述的话,就是一个字符串就是一个链表。每个Node都保存了它的所有子节点。
也就是说如果只考虑小写的26个字母,那么Trie字典树的每个节点都可能有26个子节点。
基本实现
实现一个 Trie (前缀树),包含 insert
, search
, 和 startsWith
这三个操作。
字符串中的每一个字符都会被封装为一个Node对象。
Node的组成包括两部分:
1、哈希表,以当前封装的字符为key,value是它的所有子节点被封装之后的Node对象,保存当前这个字符的所有子节点。
2、isWord属性,用于标记到此字符位置是否构成了一个单词。
class Trie{
/**
* Trie树的节点类,其中成员map记录的是某个节点的所有子节点
* key是这个节点的字符;value是存储其所有子节点的一个Node
*/
private class Node{
Node[] map = new Node[26];
boolean isWord;
}
Node root = new Node();
public Trie(){}
public void insert(String word){
insert(word,root);
}
private void insert(String word, Node node) {
if (node == null){
return;
}
if (word.length() == 0){
node.isWord = true;
return;
}
int index = getIndex(word.charAt(0));
if (node.map[index] == null){
node.map[index] = new Node();
}
insert(word.substring(1),node.map[index]);
}
public boolean search(String word){
return search(word,root);
}
private boolean search(String word, Node node) {
if (word.length() == 0){
return node.isWord;
}
int index = getIndex(word.charAt(0));
if (node.map[index] == null){
return false;
}
return search(word.substring(1),node.map[index]);
}
public boolean startsWith(String prefix){
return startWith(prefix,root);
}
private boolean startWith(String prefix, Node node) {
if (prefix.length() == 0){
return true;
}
int index = getIndex(prefix.charAt(0));
if (node.map[index] == null){
return false;
}
return startWith(prefix.substring(1),node.map[index]);
}
private int getIndex(char c){
return c - 'a';
}
}
练习:677. 键值映射
实现一个 MapSum 类,支持两个方法,insert和sum:
MapSum() 初始化MapSum对象
void insert(String key, int val) 插入 key-val 键值对,字符串表示键 key ,整数表示值 val 。如果键 key 已经存在,那么原来的键值对将被替代成新的键值对。
int sum(string prefix) 返回所有以该前缀prefix开头的键key的值的总和。
package review.str;
public class MapSum {
class Node{
Node[] map = new Node[26];
int value;
}
Node root = new Node();
public void insert(String key,int value){
insert(key,value,root);
}
private void insert(String key, int value, Node node) {
if (node == null){
return;
}
if (key.length() == 0){
node.value = value;
return;
}
int index = getIndex(key.charAt(0));
if (node.map[index] == null){
node.map[index] = new Node();
}
insert(key.substring(1),value,node.map[index]);
}
public int sum(String prefix){
return sum(prefix,root);
}
private int sum(String prefix, Node node) {
if (node == null){
return 0;
}
if (prefix.length() == 0){
int sum = node.value;
for (int i = 0; i < node.map.length; i++) {
sum += sum(prefix,node.map[i]);
}
return sum;
}else {
int index = getIndex(prefix.charAt(0));
if (node.map[index] == null){
return 0;
}
return sum(prefix.substring(1),node.map[index]);
}
}
private int getIndex(char c){
return c - 'a';
}
}