提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
前言
Trie 树又叫字典树、前缀树、单词查找树，是一种二叉树衍生出来的高级数据结构，主要应用场景是处理字符串前缀相关的操作
一、力扣211. 添加与搜索单词 - 数据结构设计
class WordDictionary {
static final int R = 26;
TrieNode root = null;
static class TrieNode{
String val;
TrieNode[] children = new TrieNode[R];
}
public WordDictionary() {
}
public void addWord(String word) {
root = put(root,word,0);
}
public boolean search(String word) {
return get(root,word,0);
}
boolean get(TrieNode node, String word, int index){
if(node == null){
return false;
}
if(index == word.length()){
if(node.val != null){
return true;
}
return false;
}
char c = word.charAt(index);
if(c == '.'){
for(int i = 0; i < R; i ++){
if(get(node.children[i],word,index+1)){
return true;
}
}
}else{
if(get(node.children[c-'a'],word,index+1)){
return true;
}
}
return false;
}
TrieNode put(TrieNode node, String word, int index){
if(node == null){
node = new TrieNode();
}
if(index == word.length()){
node.val = word;
return node;
}
char c = word.charAt(index);
node.children[c-'a'] = put(node.children[c-'a'],word,index+1);
return node;
}
}
/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary obj = new WordDictionary();
* obj.addWord(word);
* boolean param_2 = obj.search(word);
*/
二、力扣677. 键值映射
class MapSum {
static final int R = 26;
TrieNode root = null;
int sum = 0;
static class TrieNode{
int val = 0;
TrieNode[] children = new TrieNode[R];
}
public MapSum() {
}
public void insert(String key, int val) {
root = put(root,key,0,val);
}
public int sum(String prefix) {
get(root,prefix,0);
int temp = sum;
sum = 0;
return temp;
}
void get(TrieNode node, String prefix, int index){
if(node == null){
return;
}
if(index < prefix.length()){
char c = prefix.charAt(index);
// sum += node.val;
get(node.children[c-'a'],prefix,index+1);
}else{
sum += node.val;
for(int i = 0; i < R; i ++){
if(node.children[i] != null){
get(node.children[i],prefix,index+1);
}
}
}
}
TrieNode put(TrieNode node, String key, int index,int val){
if(node == null){
node = new TrieNode();
}
if(index == key.length()){
node.val = val;
return node;
}
char c = key.charAt(index);
node.children[c-'a'] = put(node.children[c-'a'],key,index+1,val);
return node;
}
}
/**
* Your MapSum object will be instantiated and called as such:
* MapSum obj = new MapSum();
* obj.insert(key,val);
* int param_2 = obj.sum(prefix);
*/
