为女人网上量体做衣网站,做企业网站 空间怎么买,做视频素材网站,ae做网站导航提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、力扣208. 实现 Trie (前缀树)二、力扣648. 单词替换 前言 Trie 树又叫字典树、前缀树、单词查找树#xff0c;是一种二叉树衍生出来的高级数据结构#x… 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 前言一、力扣208. 实现 Trie (前缀树)二、力扣648. 单词替换 前言 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],index1,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,index1,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,index1,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(ListString 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,index1);}char c dic.charAt(index);return getOne(dic, node.children[c-a],index1,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],index1,dic);return node;}}
}
