3045. 统计前后缀下标对 II（困难）

核心思想
字典树看灵神把
这里提供一个不同的版本
map存放了int[] 需重写equals 和 hashCode

class Node {
    Map<MyIntArray, Node> son = new HashMap<>();
    int cnt;
}

class MyIntArray{
    private final int[] array;

    MyIntArray(int[] array) {
        this.array = array;
    }

    public int[] getArray() {
        return array;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        MyIntArray that = (MyIntArray) o;
        return Arrays.equals(array, that.array);
    }

    @Override
    public int hashCode() {
        return Arrays.hashCode(array);
    }

}
class Solution {

    public long countPrefixSuffixPairs(String[] words) {
        long ans = 0;
        Node root = new Node();
        for (String S : words) {
            char[] s = S.toCharArray();
            int n = s.length;
            Node cur = root;
            for (int i = 0; i < n; i++) {
                int x = s[i] - 'a';
                int y = s[n - i - 1] - 'a';
                MyIntArray ints = new MyIntArray(new int[]{x, y});
                if (!cur.son.containsKey(ints)) {
                    cur.son.put(ints, new Node());
                }
                cur = cur.son.get(ints);
                ans += cur.cnt;
            }
            cur.cnt++;
        }
        return ans;
    }
}