Trie树

Trie数可以快速的存储和查询字符串集合

用法

假设给定一组字符串abc,ab,bcf,abb,ab。最后需要去查找是否存在多少个ab字符串

• 使用Trie快速的存储给定的字符串

  1. 从根节点开始
  2. 遍历每个字符串，判断该节点上是否存在相同子节点
  3. 如果存在则继续，不存在则创建
  4. 将最后一个字符标记，用于表示当前字符有存在一个字符串

• 视图

  

• 最后查找存在多少个ab字符串，只需要取出b字符对应的个数就行了

代码实现

• 重要通过数组去模拟trie

  主要要清楚son[][], cnt[], index变量的含义

  • N的大写取决于题目中最大的节点数，也就是最多有多少长度的字符串

  • 26则是默认规定都是小写字母那么最多只有26个字母

  • son[][]son是存储当前节点的子节点的下标

    🌰: son[0][1] = 2; 代表的是下标为0的节点，有子节点这个子节点为“1”（注意这个1取决与你怎么定义的，例如我可以将a表示为1，这里姑且看作字符a）2则代表这个子节点的下标

    son[2][2] = 3 仅接着上面的，这个代表的意思就是，下标为2的节点（也就是上面的“1”，看作字符a）a的子节点为“2”（这里姑且看作字符b。取决于你），3则代表这个子节点的下标

    以此类推...

  
    int N = 100010;
    int[][] son = new int[N][26];
    int ent[N];
    int index = 0;
  
  

插入函数

回忆一下步骤，先判断是否在trie树上，如果不存在则创建节点，存在则切换为对应的下标，最后将cnt[]数组对应的最后一个字符自增

  public void insert(String str) {

    int p = 0; // 存储节点的下标
    for (int i = 0; i < str.length(); i++) {
      
      int u = str.charAt(i) - 'a'; // 将son[][u] u语义化，这里将小写字母语义化为int
      
      if (son[p][u] == 0) {
        son[p][u] = ++index; // 创建节点，节点的下标通过index生成
      }

      p = son[p][u]; // 当前字符存在，则切换到该节点
    }

    cnt[p]++; // 遍历到最后一个字符说明添加完成，进行标记
  }

查询

查询的逻辑也十分类似，只要遍历到字符串中有字符不存在节点则说明，没有该字符串。当遍历到最后一个字符说明有该字符串，直接获取cnt[]中记录的个数即可

  
  public int query(String str) {

    int p = 0;

    for (int i = 0; i < str.length(); i++) {

      int u = str.charAt(i) - 'a';
      
      if (son[p][u] == 0) return 0;

      p = son[p][u];
    }

    return cnt[p];
  }

重点

• trie树思路其实并不复杂，重点在于使用二维数组去构建