力扣208题：实现Tire（前缀树）

本文主要是介绍力扣208题：实现Tire（前缀树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目链接】

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

【解题代码】

public class Trie {public class TireNode {private int level; // 所在层级private boolean end; // 是否为词尾private HashMap<Character, TireNode> nextChs; // 后续所有词节点TireNode(int level, boolean end) {this.level = level;this.end = end;}// 插入下一几点public TireNode putNext(char ch, boolean end) {TireNode newNode = new TireNode(this.level + 1, end);if (this.nextChs == null) this.nextChs = new HashMap<>();this.nextChs.put(ch, newNode);return newNode;}}private TireNode root;public Trie() {// 初始化一个根节点root = new TireNode(-1, false);}public void insert(String word) {TireNode node = match(word);for (int i = node.level + 1; i < word.length(); i++) {node = node.putNext(word.charAt(i), i == word.length() - 1);}// 这个一定要加上，因为插入词的所有字符可能都存在树里，但是作为另外某些词的一部分。node.end = true;}public boolean search(String word) {TireNode node = match(word);// 判断匹配的节点层级是否为词尾，并且此节点为词尾节点。return node.level == word.length() - 1 && node.end == true;}public boolean startsWith(String prefix) {TireNode node = match(prefix);// 判断匹配的节点层级是否为词尾return node.level == prefix.length() - 1;}// 这是插入和查找等函数的关键基础函数，通过词查找最大匹配的节点private TireNode match(String word) {TireNode node = root;char ch;for (int i = 0; i < word.length(); i++) {ch = word.charAt(i);if (node.nextChs != null && node.nextChs.containsKey(ch)) {node = node.nextChs.get(ch);} elsebreak;}return node;}public static void main(String[] args) {Trie trie = new Trie();trie.insert("apple");boolean result = trie.search("apple");   // 返回 TrueSystem.out.println("result = " + result);result = trie.search("app");     // 返回 FalseSystem.out.println("result = " + result);result = trie.startsWith("app"); // 返回 TrueSystem.out.println("result = " + result);trie.insert("app");result = trie.search("app");     // 返回 TrueSystem.out.println("result = " + result);}

【解题步骤】

1. 设计一个前缀节点类，这个类保存了，当前字符所在层级，是否为某个词的词尾，以及后续所有字符的节点，采用HashMap存储，key是后续字符，value就是下一个节点对象；

   public class TireNode {private int level; // 所在层级private boolean end; // 是否为词尾private HashMap<Character, TireNode> nextChs; // 后续所有词节点TireNode(int level, boolean end) {this.level = level;this.end = end;}// 插入下一几点public TireNode putNext(char ch, boolean end) {TireNode newNode = new TireNode(this.level + 1, end);if (this.nextChs == null) this.nextChs = new HashMap<>();this.nextChs.put(ch, newNode);return newNode;}}

   • 1 字符所在层级level变量的设计：因为词的匹配不光要字符相同，位置也要一样；

   1. 2 是否为某个词的词尾：这个变量也很重要，词尾不一定是叶子节点，因为一个词可能是另一个词的一部分
   • 3 后续所有字符对应的节点变量：采用HashMap存储，肯定是考虑性能因素，查询时间复杂度为O(1)
   1. 4 大家可以看到，这个节点类本身没有存有字符变量，而是放在上一个节点的指向本节点的key中，从减少了重复而不必要的存储；
2. 设计一个通用的匹配节点查找函数，返回与某个字符串的匹配最深节点：这个匹配函数非常重要，因为无论是插入词，判断字符串 word 在前缀树，是否存在前缀为某个字符串的词，都可以复用这个函数

   // 这是插入和查找等函数的关键基础函数，通过词查找最大匹配的节点
   private TireNode match(String word) {TireNode node = root;char ch;for (int i = 0; i < word.length(); i++) {ch = word.charAt(i);if (node.nextChs != null && node.nextChs.containsKey(ch)) {node = node.nextChs.get(ch);} elsebreak;}return node
   }

3. 实现Trie() 初始化前缀树对象：因为所有词没有统一的根字符，创建一个虚拟的空的根节点

   // 初始化一个根节点
   root = new TireNode(-1, false);

4. 编写函数void insert(String word) 向前缀树中插入字符串 word ，首先在前缀树中查找与word最深匹配的节点，然后再将后续字符一一插入树中，最后将词尾字符所在节点的end值设置为true

   public void insert(String word) {TireNode node = match(word);for (int i = node.level + 1; i < word.length(); i++) {node = node.putNext(word.charAt(i), false);}// 这个一定要加上，因为插入词的所有字符可能都存在树里，但是作为另外某些词的一部分。node.end = true;
   }

5. 编写函数boolean search(String word) ：首先在前缀树中查找与word最深匹配的节点，最后判断匹配的节点层级是否为词尾，并且此节点为词尾节点。

   public boolean search(String word) {TireNode node = match(word);// 判断匹配的节点层级是否为词尾，并且此节点为词尾节点。return node.level == word.length() - 1 && node.end == true;
   }

6. 编写函数boolean startsWith(String prefix)  ：首先在前缀树中查找与word最深匹配的节点，判断匹配的节点层级是否输入字符串的末尾

   public boolean startsWith(String prefix) {TireNode node = match(prefix);// 判断匹配的节点层级是否为输入字符串的末尾return node.level == prefix.length() - 1;
   }

【思路总结】

1. 所有树的算法题中，节点类的设计，是必不可少且非常重要，节点中的变量要点到关键并且尽量精简；
2. 这种算法题目，属于复合应用题，需要借助已有的一些数据结构，比如这里就用到了HashMap；
3. 前缀树对外提供的功能函数，要根据代码执行逻辑，找到其共性点，设计好内部通用函数，一旦内部通用函数设计好，公共的功能函数只需要在此基础上进行封装即可，达到最大的代码复用，并通过这种“正交性”分解，降解了程序的复杂性

这篇关于力扣208题：实现Tire（前缀树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---