3805. 统计凯撒加密对数目

🎯 问题描述（来源于LeetCode）

描述：
给你一个字符串数组 words，所有字符串长度相同且仅包含小写英文字母。
如果一个字符串可以通过另一个字符串进行凯撒加密（即每个字符都向后移动相同的位数，例如 ‘a’ -> ‘c’, ‘b’ -> ‘d’）得到，则称这两个字符串是相似的。
请你返回 words 中相似字符串对的数量。

说明：

这是一个哈希表计数结合差分特征提取的问题。
核心洞察：如果字符串 $A$ 和 $B$ 是凯撒加密关系（即 $B[i] = A[i] + k$ ），那么它们相邻字符之间的差值是恒定不变的。
- $B[i] - B[i-1] = (A[i] + k) - (A[i-1] + k) = A[i] - A[i-1]$ 。
因此，我们可以将每个字符串转换为其“差分序列”作为特征指纹。指纹相同的字符串属于同一组凯撒加密类。
示例：
示例 1：

输入：words = ["ab", "bc", "cd", "xy", "yz"]
输出：4
解释：
- "ab" 的差分特征：(1)
- "bc" 的差分特征：(1)
- "cd" 的差分特征：(1)
- "xy" 的差分特征：(1)
- "yz" 的差分特征：(1)
- 这 5 个字符串的差分特征都相同，属于同一类。
- 对数 = C(5, 2) = 10。

💻 解题思路

思路1：哈希表 + 差分指纹

思路1：代码实现

class Solution:
    def countPairs(self, words: List[str]) -> int:
        m = len(words[0])
        ans = 0
        count = defaultdict(int)
        
        for s in words:
            x = []
            # 1. 计算相邻字符的差值（构建差分指纹）
            for i in range(1, m):
                # 计算 s[i] - s[i-1]
                # +26 % 26 用于处理负数，确保差值在 0-25 之间
                diff = (ord(s[i]) - ord(s[i-1]) + 26) % 26
                x.append(diff)
            
            # 2. 处理循环/首尾差值
            # 代码逻辑中包含了一项特殊的差值：s[m-1] - s[0]
            # 这使得特征向量更加唯一，能够区分某些仅靠相邻差值无法区分的模式
            # 例如 "aba" 和 "bab" 的相邻差值序列可能相同，但首尾差值不同
            circular_diff = (ord(s[m-1]) - ord(s[0]) + 26) % 26
            x.append(circular_diff)
            
            # 3. 将列表转为元组，作为哈希表的键
            x = tuple(x)
            
            # 4. 累加计数（枚举右，维护左）
            if x in count:
                ans += count[x]
            
            count[x] += 1
            
        return ans

思路1：📊 性能分析

时间复杂度： $O(N \times M)$ $O (N \times M)$
- 其中 $N$ 是 words 的长度， $M$ 是每个字符串的长度。
- 我们需要遍历每个字符串，并对每个字符串遍历其字符以计算差分。
空间复杂度： $O(N \times M)$ $O (N \times M)$
- 哈希表存储差分元组。在最坏情况下，所有字符串的差分特征都不同，需要存储 $N$ 个长度为 $M$ 的元组。

思考

凯撒加密的不变性：
- 凯撒加密本质是给字符串加了一个常数偏移量 $k$ 。
- 在数学上，求导（差分）可以消除常数项。
- 因此，差分序列是识别凯撒加密字符串的最佳指纹。
代码中的特殊处理：
- 代码中不仅计算了 s[i] - s[i-1]，还额外计算了 s[m-1] - s[0] 并加入特征向量。
- 这一项实际上是前面所有差分的总和的相反数（在模运算下）。虽然从数学上讲，前 $m-1$ 个差分已经确定了字符串的形状，但加上这一项可以作为校验，或者用于处理特定的循环移位情况，确保特征的唯一性。
模运算：
- (val + 26) % 26 是处理字母表循环的标准技巧。
- 例如，'a' - 'z' 应该是 1（a 在 z 后面 1 位），直接计算是 -25，通过公式变为 1。
累加计数：
- 依然是经典的 ans += count[key] 模式。
- 每遇到一个同类的字符串，它就能和之前所有的同类字符串组成新的一对。