leetcode刷题 | 关于前缀树的题型总结

题目链接

208. 实现 Trie (前缀树) - 力扣（LeetCode）

648. 单词替换 - 力扣（LeetCode）

676. 实现一个魔法字典 - 力扣（LeetCode）

820. 单词的压缩编码 - 力扣（LeetCode）

677. 键值映射 - 力扣（LeetCode）

421. 数组中两个数的最大异或值 - 力扣（LeetCode）

实现 Trie (前缀树)

前缀树是一种数据结构，一般用于高效存储和检索字符串的键。

class Trie {TreeNode root;class TreeNode{TreeNode[] next;boolean isEnd;public TreeNode(){// 子节点的指针数组，长度为26，可以包含所有的小写字母next = new TreeNode[26];// 表示是否为字符串的结尾this.isEnd = false;}}public Trie() {// 初始化root = new TreeNode();}public void insert(String word) {TreeNode cur = root;// 将当前字符串插入到前缀树中for(char c : word.toCharArray()){// 如果不存在那么新建一个前缀树节点，进行插入// 如果存在那么指针移动到下一个节点，处理下一个字符if(cur.next[c-'a'] == null) cur.next[c-'a'] =new TreeNode();cur = cur.next[c-'a'];}// 插入完毕标记到了结尾cur.isEnd = true;}public boolean search(String word) {TreeNode cur = root;for(char c: word.toCharArray()){// 如果当前节点不存在，那么直接返回false，前缀树中没有这个字符串if(cur.next[c-'a'] == null) return false;cur = cur.next[c-'a'];// 继续处理下一个字符节点}return cur.isEnd; //返回是否结束，如果字符串没有结束那么也不包含该字符串}public boolean startsWith(String prefix) {TreeNode cur = root;for(char c: prefix.toCharArray()){// 如果不存在，那么不存在该前缀if(cur.next[c-'a'] == null) return false;cur = cur.next[c-'a'];}return true;}
}

单词替换

使用前缀树构造一颗字典树，将所有的词根都放入到前缀树中，遍历句子中的每一个单词，对单词在字典中进行词根搜索，找到对应的词根，用找到的词根换当前单词

class Solution {TrieNode root = new TrieNode();class TrieNode{TrieNode[] next ;boolean isEnd;public TrieNode(){next = new TrieNode[26];isEnd = false;}}// 将词根插入到字典树(前缀树)中public void insert(String word,TrieNode root){TrieNode node = root;for(char c:word.toCharArray()){if(node.next[c-'a'] == null) node.next[c-'a']=new TrieNode();node = node.next[c-'a'];}node.isEnd = true;}// 查找字符串中的词根public boolean search(TrieNode root,String word){TrieNode node = root;for(char c:word.toCharArray()){if(node.isEnd == true) break;if(node.next[c-'a'] == null) return false;node = node.next[c-'a'];}return true;}// 进行替换public String replace(String word,TrieNode root){StringBuilder sb = new StringBuilder();TrieNode node = root;for(char c: word.toCharArray()){// 如果当前节点为末尾，跳出循环，返回当前找到的词根if(node.isEnd) break;// 处理下一个节点node = node.next[c-'a'];// 将当前词根加入到字符串中sb.append(c);}return sb.toString();}public String replaceWords(List dictionary, String sentence) {// 插入词根for(String s: dictionary) insert(s,root);String[] split = sentence.split(" ");for (int i = 0; i < split.length; i++) {// 进行替换if (search(root,split[i])) split[i] = replace(split[i],root);}StringBuilder sb = new StringBuilder();for(String s: split){sb.append(s+" ");}sb.deleteCharAt(sb.length()-1);return sb.toString();}
}

实现一个魔法字典

class MagicDictionary {class Trie {boolean isFinished;Trie[] child;public Trie() {isFinished = false;child = new Trie[26];}}Trie root;public MagicDictionary() {root = new Trie();}public void buildDict(String[] dictionary) {for (String word : dictionary) {Trie cur = root;for (int i = 0; i < word.length(); ++i) {char ch = word.charAt(i);int idx = ch - 'a';if (cur.child[idx] == null) {cur.child[idx] = new Trie();}cur = cur.child[idx];}cur.isFinished = true;}}public boolean search(String searchWord) {return dfs(searchWord, root, 0, false);}private boolean dfs(String searchWord, Trie node, int pos, boolean modified) {if (pos == searchWord.length()) {return modified && node.isFinished;}int idx = searchWord.charAt(pos) - 'a';if (node.child[idx] != null) {if (dfs(searchWord, node.child[idx], pos + 1, modified)) {return true;}}if (!modified) {for (int i = 0; i < 26; ++i) {if (i != idx && node.child[i] != null) {if (dfs(searchWord, node.child[i], pos + 1, true)) {return true;}}}}return false;}
}

我觉得遍历查找的方式就很好了，前缀树多少有点绕圈子b(￣▽￣)d

class MagicDictionary {String[] words;/** Initialize your data structure here. */public MagicDictionary() {}public void buildDict(String[] dictionary) {words = dictionary;}public boolean search(String searchWord) {for(String s: words){// 标记一个字符串中字符与词根中字符不同的个数int diff = 0;if(s.length() != searchWord.length()) continue;for(int i = 0;iif(s.charAt(i) != searchWord.charAt(i)) {diff++;// 大于1个那么直接跳出循环，返回false，不能够转换一次就和词根一样if(diff > 1) break;}}// 如果为1，那么可以转换if(diff == 1) return true;}return false;}
}

单词的压缩编码

保留所有不是其他单词后缀的单词

将所有的字符倒着插入到前缀树中，如果找到了

class Solution {public int minimumLengthEncoding(String[] words) {TrieNode root = new TrieNode();HashMap map = new HashMap(); for(int i = 0;iString s = words[i];TrieNode node = root;for(int j = s.length()-1;j>=0;j--){// 倒着插入前缀树// 得到当前节点node = node.get(s.charAt(j));}// 将节点和当前字符的下标存入到map中map.put(node,i);}int res = 0;for(TrieNode node : map.keySet()){// 遍历map// 如果当前节点的count = 0，说明为叶子节点，叶子结点就是不是后缀的单词// 取出map中的保存的下标，将所有不是后缀的单词长度相加// +1 是 +#if(node.count == 0) res+=words[map.get(node)].length()+1;}     return res;}class TrieNode{TrieNode[] children;int count;public TrieNode(){children = new TrieNode[26];count = 0;}public TrieNode get(char c){if(children[c-'a'] == null){// 前缀树中没有当前字符，创建前缀树节点children[c-'a'] = new TrieNode();count ++; // 长度为1}// 如果前缀树中存在当前字符，那么该字符为某一个单词的后缀，直接返回当前节点，当前节点的值为1// 后续判断中会用到return children[c-'a']; // 返回当前节点}}
}

键值映射

class MapSum {TrieNode root;HashMap map;public MapSum() {root = new TrieNode();map = new HashMap();}// 插入public void insert(String key, int val) {// 当前值-map中包含该键的值，增量int d = val-map.getOrDefault(key,0);// 将key和val存入到mapmap.put(key,val);TrieNode cur = root;for(char c : key.toCharArray()){// 遍历key的字符// 字符节点为空，新建一个节点if(cur.next[c-'a'] == null){cur.next[c-'a'] = new TrieNode();}// 继续处理下一个节点cur = cur.next[c-'a'];// 需要更新每个前缀对应的值// 把每一个节点都加增量，以便后续计算以某前缀开头所有key的和cur.val += d;}}// 以某前缀开头所有key的和public int sum(String prefix) {TrieNode cur = root;for(char c: prefix.toCharArray()){// 如果当前节点为空，那么没有前缀树中不存在该前缀，直接返回0if(cur.next[c-'a'] == null) return 0;cur = cur.next[c-'a'];}// 直接返回当前节点的值，就为和return cur.val;}class TrieNode{TrieNode[] next;int val;public TrieNode(){next = new TrieNode[26];val = 0;}}
}

这道题我也觉得HashMap最好用，直接使用哈希中封装好的函数👍

class MapSum {HashMap map;/** Initialize your data structure here. */public MapSum() {map = new HashMap();}public void insert(String key, int val) {map.put(key,val);}public int sum(String prefix) {int res = 0;for(String s:map.keySet()){if(s.startsWith(prefix)) res += map.get(s);}return res;}
}

数组中两个数的最大异或值

异或就是当位两个数的值不同才为1，所以需要尽量找到一个与当前位不同的数

先确定高位，再确定低位，才能保证最大 ，接着一位一位去确定这个数位的大小

class Solution {class TrieNode{TrieNode[] next;public TrieNode(){next = new TrieNode[2];}}TrieNode root = new TrieNode();public int findMaximumXOR(int[] nums) {int max = Integer.MIN_VALUE;for (int num:nums){inster(num);max = Math.max(max,maxOR(num));}return  max;}public void inster(int num){TrieNode node = root;// 倒着取出，先得到最低位for(int i = 31;i>=0;i--){int d = num >> i & 1; //取出第i位的数if (node.next[d] == null) node.next[d] = new TrieNode();node = node.next[d];}}public int maxOR(int num){TrieNode node = root;int res = 0;for (int i = 31;i>=0;i--){int d = num >>i & 1;// 由于异或要最大，则尽量走与 num 当前二进制位 d 相反的一位，// 如果相反的一位为空，则只好走相同的一位了。int opposite = (d==0)?  1 : 0; //为了让异或结果最大，选择不同的二进制进行异或if (node.next[opposite] != null){res = res*2+opposite; //因为是二进制所以*2node = node.next[opposite];}else{//如果不存在这样的数，就先选择相同的res = res*2+d;node = node.next[d];}}return  num^res;}}