提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
前言
Trie 树又叫字典树、前缀树、单词查找树，是一种二叉树衍生出来的高级数据结构，主要应用场景是处理字符串前缀相关的操作
一、力扣208. 实现 Trie (前缀树)
class Trie {
private int size;
private static final int R = 58;
private TrieNode root = null;
static class TrieNode{
String val;
TrieNode[] chialdren = new TrieNode[R];
}
public Trie() {
this.size = 0;
}
public void insert(String word) {
this.root = put(root,0,word);
}
public boolean search(String word) {
return get(word,0,root);
}
public boolean startsWith(String prefix) {
return getPrefix(prefix,0,root);
}
public TrieNode put(TrieNode node,int index,String word){
if(node == null){
node = new TrieNode();
}
if(index == word.length()){
node.val = word;
return node;
}
char c = word.charAt(index);
node.chialdren[c-'A'] = put(node.chialdren[c-'A'],index+1,word);
return node;
}
public boolean get(String word,int index,TrieNode node){
if(node == null){
return false;
}
if(index == word.length()){
if(node.val != null){
return true;
}else{
return false;
}
}
char c = word.charAt(index);
if(get(word,index+1,node.chialdren[c-'A'])){
return true;
}
return false;
}
public boolean getPrefix(String word,int index,TrieNode node){
if(node == null){
return false;
}
if(index == word.length()){
return true;
}
char c = word.charAt(index);
if(getPrefix(word,index+1,node.chialdren[c-'A'])){
return true;
}
return false;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/
二、力扣648. 单词替换
class Solution {
public String replaceWords(List<String> dictionary, String sentence) {
Trie trie = new Trie();
for(int i = 0; i < dictionary.size(); i ++){
trie.put(dictionary.get(i));
}
StringBuilder sb = new StringBuilder(sentence);
StringBuilder res = new StringBuilder();
for(int i = 0, j = 0; j <= sentence.length(); j++) {
if(j < sentence.length() && sb.charAt(j) != ' '){
continue;
} else {
String cur = trie.get(sb.substring(i, j));
res.append(cur);
if (j < sentence.length()) {
res.append(" ");
}
i = j + 1;
}
}
return res.toString();
}
class Trie{
static final int R = 26;
TrieNote root = null;
static class TrieNote{
String val;
TrieNote[] children = new TrieNote[R];
}
String get(String dic){
int len = Integer.MAX_VALUE;
return getOne(dic, root, 0, len);
}
String getOne(String dic, TrieNote node, int index, int len){
if(node == null || index == dic.length()){
return len == Integer.MAX_VALUE ? dic : dic.substring(0,len-1);
}
if(node.val != null){
len = Math.min(len,index+1);
}
char c = dic.charAt(index);
return getOne(dic, node.children[c-'a'],index+1,len);
}
void put(String dic){
this.root = putA(root,0,dic);
}
TrieNote putA(TrieNote node, int index, String dic){
if(node == null){
node = new TrieNote();
}
if(index == dic.length()){
node.val = dic;
return node;
}
char c = dic.charAt(index);
node.children[c-'a'] = putA(node.children[c-'a'],index+1,dic);
return node;
}
}
}
