2026-05-18：统计凯撒加密对数目。用go语言，给定一个长度都为 m、只含小写字母的字符串数组 words（共 n 个）。如果可以通过对两个字符串 s、t 反复执行同一种“整体循环右移字母”的操

2026-05-18：统计凯撒加密对数目。用go语言，给定一个长度都为 m、只含小写字母的字符串数组 words（共 n 个）。如果可以通过对两个字符串 s、t 反复执行同一种“整体循环右移字母”的操作，使它们最终完全一致，那么称 s 与 t 相似。

具体操作是：你可以任选一个当前的字符串，把其中每个字母都替换成字母表中紧接着的下一个字母（例如 z 变成 a）。你可以对 s 或 t 进行任意次（可能为 0 次）这种操作。

现在要统计满足 i < j 且 words[i] 与 words[j] 相似的下标对 (i, j) 的数量，并返回这个数量。

1 <= n == words.length <= 100000。

1 <= m == words[i].length <= 100000。

1 <= n * m <= 100000。

words[i] 仅由小写英文字母组成。

输入： words = [“ab”,“aa”,“za”,“aa”]。

输出： 2。

解释：

words[0] = “ab” 和 words[2] = “za” 是相似的。words[1] = “aa” 和 words[3] = “aa” 是相似的。

题目来自力扣3805。

完整执行步骤

第一步：统计原始字符串的出现次数

1. 遍历输入数组["ab","aa","za","aa"]
2. 用哈希表记录每个字符串出现了几次：
   • "ab"：出现 1 次
   • "aa"：出现 2 次
   • "za"：出现 1 次
3. 这一步的作用：避免重复处理相同字符串，直接用计数计算组合数，提升效率。

第二步：核心转换 —— 生成「标准化特征字符串」

这是判断相似的关键：把所有相似的字符串，转换成同一个唯一的特征字符串。
转换规则：
对一个字符串，计算每个字符和第一个字符的相对偏移（循环26个字母），最终得到一个只由相对差值组成的新字符串，这就是它的标准化特征。

逐个处理每个原始字符串：

1. 处理 “ab”
   • 第一个字符是a
   • 转换：a-a=0，b-a=1→ 特征字符串：[0,1]
2. 处理 “aa”
   • 第一个字符是a
   • 转换：a-a=0，a-a=0→ 特征字符串：[0,0]
3. 处理 “za”
   • 第一个字符是z
   • 转换：z-z=0，a-z=1（循环后）→ 特征字符串：[0,1]

✅ 结论：

• ab和za特征相同 → 相似
• 两个aa特征相同 → 相似

第三步：统计符合条件的字符串对数量

使用哈希表记录每个特征字符串已经出现的总次数，结合组合数学计算对数：
组合公式：从c个相同元素中选 2 个的数量 =c*(c-1)/2

逐特征计算：

1. 初始化：空哈希表（存特征→总次数），答案=0
2. 处理特征[0,1]（对应原始字符串ab，数量1）
   • 哈希表中无此特征，新增：[0,1] → 1
   • 组合数：1*0/2=0 → 答案仍为 0
3. 处理特征[0,0]（对应原始字符串aa，数量2）
   • 哈希表中无此特征，新增：[0,0] → 2
   • 组合数：2*1/2=1 → 答案 = 0+1 =1
4. 处理特征[0,1]（对应原始字符串za，数量1）
   • 哈希表中已有此特征（次数=1）
   • 新增对数：1*1 = 1
   • 组合数：1*0/2=0
   • 总答案 = 1+1+0 =2
   • 更新哈希表：[0,1] → 1+1=2

第四步：返回最终结果

最终统计的有效对数为2，和题目要求的输出完全一致。

时间复杂度 & 额外空间复杂度

1. 总时间复杂度

O(n × m)

• n：字符串的个数
• m：每个字符串的长度
• 解释：
  1. 遍历所有字符串统计次数：O(n)
  2. 为每个字符串生成标准化特征：需要遍历字符串的每一个字符，总字符数 = n×m
  3. 哈希表操作都是 O(1) 平均时间
• 题目限制n×m ≤ 10^5，这个复杂度完全满足要求。

2. 总额外空间复杂度

O(n × m)

• 解释：
  1. 两个哈希表：存储原始字符串、标准化特征字符串
  2. 所有标准化特征的总长度 = 总字符数 n×m
• 空间占用与输入总字符数成正比，是最优的空间复杂度。

总结

1. 核心思路：把相似字符串统一转为相同的标准化特征，用特征分组统计；
2. 计算方式：用组合计数快速统计每一组内的有效字符串对；
3. 最终效率：时间 O(n×m)，空间 O(n×m)，完美适配题目数据规模。

Go完整代码如下：

packagemainimport("fmt")funccountPairs(words[]string)int64{cntWords:=map[string]int{}for_,s:=rangewords{cntWords[s]++}ans:=0cnt:=map[string]int{}fors,c:=rangecntWords{t:=[]byte(s)base:=t[0]fori:=ranget{t[i]=(t[i]-base+26)%26// 保证结果在 [0, 25] 中}s=string(t)ans+=cnt[s]*c+c*(c-1)/2// c 个 s 中选 2 个有 C(c, 2) 种方案cnt[s]+=c}returnint64(ans)}funcmain(){words:=[]string{"ab","aa","za","aa"}result:=countPairs(words)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-defcount_pairs(words):# Count occurrences of each wordcnt_words={}forsinwords:cnt_words[s]=cnt_words.get(s,0)+1ans=0cnt={}fors,cincnt_words.items():# Convert string to list of bytes (characters)t=list(s)base=ord(t[0])# Get ASCII value of first character# Transform each characterforiinrange(len(t)):# (t[i] - base + 26) % 26t[i]=chr((ord(t[i])-base+26)%26+ord('a'))transformed_s=''.join(t)# ans += cnt[s]*c + c*(c-1)//2ans+=cnt.get(transformed_s,0)*c+c*(c-1)//2# cnt[s] += ccnt[transformed_s]=cnt.get(transformed_s,0)+creturnansdefmain():words=["ab","aa","za","aa"]result=count_pairs(words)print(result)if__name__=="__main__":main()

C++完整代码如下：

#include<iostream>#include<vector>#include<string>#include<unordered_map>#include<map>usingnamespacestd;longlongcountPairs(vector<string>&words){unordered_map<string,int>cntWords;for(conststring&s:words){cntWords[s]++;}longlongans=0;unordered_map<string,int>cnt;for(constauto&entry:cntWords){string s=entry.first;intc=entry.second;string t=s;charbase=t[0];for(inti=0;i<t.length();i++){t[i]=(t[i]-base+26)%26;// 保证结果在 [0, 25] 中}ans+=(longlong)cnt[t]*c+(longlong)c*(c-1)/2;cnt[t]+=c;}returnans;}intmain(){vector<string>words={"ab","aa","za","aa"};longlongresult=countPairs(words);cout<<result<<endl;return0;}