力扣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);
            } else
                break;
        }
        return node;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        boolean result = trie.search("apple");   // 返回 True
        System.out.println("result = " + result);
        result = trie.search("app");     // 返回 False
        System.out.println("result = " + result);
        result = trie.startsWith("app"); // 返回 True
        System.out.println("result = " + result);
        trie.insert("app");
        result = trie.search("app");     // 返回 True
        System.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);
           } else
               break;
       }
      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), i == word.length() - 1);
       }
       // 这个一定要加上，因为插入词的所有字符可能都存在树里，但是作为另外某些词的一部分。
       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. 前缀树对外提供的功能函数，要根据代码执行逻辑，找到其共性点，设计好内部通用函数，一旦内部通用函数设计好，公共的功能函数只需要在此基础上进行封装即可，达到最大的代码复用，并通过这种“正交性”分解，降解了程序的复杂性