字典树Tire题集

LeetCode3045

​ 讲一下这道题使用字典树的做法，首先介绍一下什么是字典树。字典树是一种处理字符串的数据结构，通常用于快速统计某些字符串出现的次数，比如：给定一个字符串数组[a,a,c,abc,ab],以下就是该字符串数组形成的字典树。

​ 这棵树可以表示以字符串a出现了2次，ab出现了1次，abc出现了1次，c出现了1次

​ 这道题的特别之处在于，不仅要求我们匹配前缀还要匹配后缀。比如ab虽然是abc的前缀但不是它的后缀，因此不符合题意。这里灵神提供的一种思路是将前缀和后缀综合考虑，比如字符串abcde、abcdesabcde，将它们的前后缀综合考虑变为{(a,e),(b,d),(c,c),(d,b),(e,a)},{(a,e),(b,d),(c,c),(d,b),(e,a),(s,s),…},可以发现经过这样转化后，只需判断前者是否是后者的前缀即可判定，某个字符串是否既是另一个字符串的前缀，又是另一个字符串的后缀，而这样就可以直接使用字典树解决。为了进一步简化，我们可以将这个键值对映射为一个数字。

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public long countPrefixSuffixPairs(String[] words) {
        int n = words.length;
        Node root = new Node();

        long res = 0l;
        for(int i = 0; i < n; i ++){
            char s[] = words[i].toCharArray();
            Node cur = root;//每次都需要从根节点开始遍历
            for(int j = 0; j < s.length; j ++){
                //将键值对映射为一个数字，一种简单的哈希
                int pair = (s[j] - 'a') << 5 | (s[s.length - 1 - j] - 'a');
                cur = cur.son.computeIfAbsent(pair,k -> new Node());
                res += cur.cnt;
            }
            cur.cnt++;
        }
        return res;
    }
}
class Node{
    int cnt;
    Map<Integer,Node>son = new HashMap<>();
}