力扣labuladong一刷day54天前缀树

一、208. 实现 Trie (前缀树)

题目链接：https://leetcode.cn/problems/implement-trie-prefix-tree/description/?utm_source=LCUS&utm_medium=ip_redirect&utm_campaign=transfer2china
思路：类似于下图就是前缀树，本质是多叉树，只不过表示子节点的数组是通过字母进行索引的，叶子节点有值来表示。

class Trie {Node root = null;class Node{int v = 0;Node[] child = new Node[26];}public Trie() {}public void insert(String word) {if (search(word)) {return;}root = addNode(root, word, 0);}public boolean search(String word) {Node node = getNode(root, word);if (node == null || node.v == 0) {return false;}return true;}public boolean startsWith(String prefix) {return getNode(root, prefix) != null;}Node getNode(Node node, String word) {Node p = node;for (int i = 0; i < word.length(); i++) {if (p == null) {return null;}p = p.child[word.charAt(i)-'a'];}return p;}Node addNode(Node node, String word, int i) {if (node == null) {node = new Node();}if (i == word.length()) {node.v = 1;return node;}int c = word.charAt(i) - 'a';node.child[c] = addNode(node.child[c], word, i+1);return node;}
}/*** 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. 单词替换

题目链接：https://leetcode.cn/problems/replace-words/description/?utm_source=LCUS&utm_medium=ip_redirect&utm_campaign=transfer2china
思路：和上题一样，也是前缀树的应用，只不过多了一个最短前缀替换。

class Solution {public String replaceWords(List<String> dictionary, String sentence) {Trie trie = new Trie();for (String s : dictionary) {trie.insert(s);}String[] split = sentence.split(" ");StringBuilder bf = new StringBuilder();for (String s : split) {String ms = trie.minSearch(s);if ("".equals(ms)) {bf.append(s);}else {bf.append(ms);}bf.append(" ");}bf.deleteCharAt(bf.length()-1);return bf.toString();}class Node {int v = 0;Node[] child = new Node[26];}class Trie {Node root = null;void insert(String word) {root = addNode(root, word, 0);}String minSearch(String word) {Node p = root;for (int i = 0; i < word.length(); i++) {if (p == null) return "";if (p.v == 1) {return word.substring(0, i);}p = p.child[word.charAt(i)-'a'];}if (p != null && p.v == 1) return word;return "";}boolean search(String word) {Node node = getNode(word);if (node == null || node.v == 0) return false;return true;}Node getNode(String word) {Node p = root;for (int i = 0; i < word.length(); i++) {if (p == null) return null;p = p.child[word.charAt(i)-'a'];}return p;}Node addNode(Node node, String word, int i) {if (node == null) {node = new Node();}if (i == word.length()) {node.v = 1;return node;}int c = word.charAt(i)-'a';node.child[c] = addNode(node.child[c], word, i+1);return node;}}
}

三、211. 添加与搜索单词 - 数据结构设计

题目链接：https://leetcode.cn/problems/design-add-and-search-words-data-structure/description/
思路：本题还是前缀树，和上一题类似，唯一不同的点是多了一个模式串匹配。

class WordDictionary {Node root = null;public WordDictionary() {}public void addWord(String word) {root = addNode(root, word, 0);}public boolean search(String word) {return traverse(root, word, 0);}boolean traverse(Node node, String word, int i) {if (node == null) return false;if (i == word.length()) {return node.v == 1;}if ('.' == word.charAt(i)) {for (int j = 0; j < 26; j++) {boolean flag = traverse(node.child[j], word, i + 1);if (flag) return flag;}}else {return traverse(node.child[word.charAt(i)-'a'], word, i+1);}return false;}Node addNode(Node node, String word, int i) {if (node == null) {node = new Node();}if (i == word.length()) {node.v = 1;return node;}int c = word.charAt(i)-'a';node.child[c] = addNode(node.child[c], word, i+1);return node;}}
class Node {int v;Node[] child = new Node[26];
}/*** Your WordDictionary object will be instantiated and called as such:* WordDictionary obj = new WordDictionary();* obj.addWord(word);* boolean param_2 = obj.search(word);*/

四、1804. 实现 Trie （前缀树） II

题目链接：https://leetcode.cn/problems/implement-trie-ii-prefix-tree/description/?utm_source=LCUS&utm_medium=ip_redirect&utm_campaign=transfer2china
思路：本题的前缀树多增加了一个功能就是删除节点，删除节点要考虑的就比较多了，到达value的位置要把数量减一，然后在后序位置删除，如果值大于0直接返回就行，不用删除节点，如果值不大于0就需要看该节点的child是否全为null，如果是返回Null就删除了，不是的话保留。

class Trie {Node root;public Trie() {}public void insert(String word) {root = addNode(root, word, 0);}public int countWordsEqualTo(String word) {Node node = getNode(word);if (null == node) return 0;return node.v;}public int countWordsStartingWith(String prefix) {Node node = getNode(prefix);if (node == null) return 0;return traverse(node, 0);}public void erase(String word) {if (getNode(word) == null) return;root = deleteNode(root, word, 0);}Node deleteNode(Node node, String word, int i) {if (node == null) return null;if (i == word.length()) {if (node.v > 0) node.v--;}else {int c = word.charAt(i)-'a';node.child[c] = deleteNode(node.child[c], word, i+1);}if (node.v > 0) return node;for (int j = 0; j < 26; j++) {if (node.child[j] != null) {return node;}}return null;}int traverse(Node node, int num) {if (node == null) return 0;num = node.v;for (int i = 0; i < 26; i++) {num += traverse(node.child[i], num);}return num;}Node addNode(Node node, String word, int i) {if (node == null) {node = new Node();}if (i == word.length()) {node.v += 1;return node;}int c = word.charAt(i)-'a';node.child[c] = addNode(node.child[c], word, i+1);return node;}Node getNode(String word) {Node p = root;for (int i = 0; i < word.length(); i++) {if (p == null) return null;p = p.child[word.charAt(i)-'a'];}return p;}
}
class Node{int v = 0;Node[] child = new Node[26];
}/*** Your Trie object will be instantiated and called as such:* Trie obj = new Trie();* obj.insert(word);* int param_2 = obj.countWordsEqualTo(word);* int param_3 = obj.countWordsStartingWith(prefix);* obj.erase(word);*/

五、677. 键值映射

题目链接：https://leetcode.cn/problems/map-sum-pairs/description/?utm_source=LCUS&utm_medium=ip_redirect&utm_campaign=transfer2china
思路：关键点是前缀查询，先获取到前缀的节点，然后广度优先遍历，前序位置记录节点位置。

class MapSum {Node root = null;public MapSum() {}public void insert(String key, int val) {root = addNode(root, key, val, 0);}public int sum(String prefix) {Node node = getNode(prefix);if (node == null) return 0;return traverse(node, 0);}int traverse(Node node, int num) {if (node == null) return 0;num = node.v;for (int i = 0; i < 26; i++) {num += traverse(node.child[i], num);}return num;}Node getNode(String word) {Node p = root;for (int i = 0; i < word.length(); i++) {if (p == null) return null;p = p.child[word.charAt(i)-'a'];}return p;}Node addNode(Node node, String word, int value, int i) {if (node == null) {node = new Node();}if (i == word.length()) {node.v = value;return node;}int c = word.charAt(i) - 'a';node.child[c] = addNode(node.child[c], word, value, i+1);return node;}}
class Node {int v = 0;Node[] child = new Node[26];
}