3805. Count Caesar Cipher Pairs

You are given an array words of n strings. Each string has length m and contains only lowercase English letters.

Two strings s and t are similar if we can apply the following operation any number of times (possibly zero times) so that s and t become equal.

• Choose either s or t.
• Replace every letter in the chosen string with the next letter in the alphabet cyclically. The next letter after 'z' is 'a'.

Count the number of pairs of indices (i, j) such that:

• i < j
• words[i] and words[j] are similar.

Return an integer denoting the number of such pairs.

struct Trie {
    int cnt;
    Trie* next[26];
    Trie() {
        memset(next, 0, sizeof next);
        cnt = 0;
    }
    int insert(string& s, int pos) {
        if(s.length() == pos) {
            cnt++;
            return cnt - 1;
        } else {
            if(!next[s[pos]-'a']) next[s[pos]-'a'] = new Trie();
            return next[s[pos]-'a']->insert(s,pos+1);
        }
    }
};
class Solution {
    string convert(string& s) {
        int diff = s[0] - 'a';
        for(auto& ch : s) ch = (ch - 'a' - diff + 26) % 26 + 'a'; 
        return s;
    }
public:
    long long countPairs(vector<string>& words) {
        long long res = 0;
        Trie* t = new Trie();
        for(auto& w : words) {
            string s = convert(w);
            res += t->insert(s,0);
        }
        return res;
    }
};