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。完整执行步骤第一步统计原始字符串的出现次数遍历输入数组[ab,aa,za,aa]用哈希表记录每个字符串出现了几次ab出现 1 次aa出现 2 次za出现 1 次这一步的作用避免重复处理相同字符串直接用计数计算组合数提升效率。第二步核心转换 —— 生成「标准化特征字符串」这是判断相似的关键把所有相似的字符串转换成同一个唯一的特征字符串。转换规则对一个字符串计算每个字符和第一个字符的相对偏移循环26个字母最终得到一个只由相对差值组成的新字符串这就是它的标准化特征。逐个处理每个原始字符串处理 “ab”第一个字符是a转换a-a0b-a1→ 特征字符串[0,1]处理 “aa”第一个字符是a转换a-a0a-a0→ 特征字符串[0,0]处理 “za”第一个字符是z转换z-z0a-z1循环后→ 特征字符串[0,1]✅ 结论ab和za特征相同 → 相似两个aa特征相同 → 相似第三步统计符合条件的字符串对数量使用哈希表记录每个特征字符串已经出现的总次数结合组合数学计算对数组合公式从c个相同元素中选 2 个的数量 c*(c-1)/2逐特征计算初始化空哈希表存特征→总次数答案0处理特征[0,1]对应原始字符串ab数量1哈希表中无此特征新增[0,1] → 1组合数1*0/20 → 答案仍为 0处理特征[0,0]对应原始字符串aa数量2哈希表中无此特征新增[0,0] → 2组合数2*1/21 → 答案 01 1处理特征[0,1]对应原始字符串za数量1哈希表中已有此特征次数1新增对数1*1 1组合数1*0/20总答案 110 2更新哈希表[0,1] → 112第四步返回最终结果最终统计的有效对数为2和题目要求的输出完全一致。时间复杂度 额外空间复杂度1. 总时间复杂度O(n × m)n字符串的个数m每个字符串的长度解释遍历所有字符串统计次数O(n)为每个字符串生成标准化特征需要遍历字符串的每一个字符总字符数 n×m哈希表操作都是 O(1) 平均时间题目限制n×m ≤ 10^5这个复杂度完全满足要求。2. 总额外空间复杂度O(n × m)解释两个哈希表存储原始字符串、标准化特征字符串所有标准化特征的总长度 总字符数 n×m空间占用与输入总字符数成正比是最优的空间复杂度。总结核心思路把相似字符串统一转为相同的标准化特征用特征分组统计计算方式用组合计数快速统计每一组内的有效字符串对最终效率时间 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]-base26)%26// 保证结果在 [0, 25] 中}sstring(t)anscnt[s]*cc*(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)1ans0cnt{}fors,cincnt_words.items():# Convert string to list of bytes (characters)tlist(s)baseord(t[0])# Get ASCII value of first character# Transform each characterforiinrange(len(t)):# (t[i] - base 26) % 26t[i]chr((ord(t[i])-base26)%26ord(a))transformed_s.join(t)# ans cnt[s]*c c*(c-1)//2anscnt.get(transformed_s,0)*cc*(c-1)//2# cnt[s] ccnt[transformed_s]cnt.get(transformed_s,0)creturnansdefmain():words[ab,aa,za,aa]resultcount_pairs(words)print(result)if__name____main__:main()C完整代码如下#includeiostream#includevector#includestring#includeunordered_map#includemapusingnamespacestd;longlongcountPairs(vectorstringwords){unordered_mapstring,intcntWords;for(conststrings:words){cntWords[s];}longlongans0;unordered_mapstring,intcnt;for(constautoentry:cntWords){string sentry.first;intcentry.second;string ts;charbaset[0];for(inti0;it.length();i){t[i](t[i]-base26)%26;// 保证结果在 [0, 25] 中}ans(longlong)cnt[t]*c(longlong)c*(c-1)/2;cnt[t]c;}returnans;}intmain(){vectorstringwords{ab,aa,za,aa};longlongresultcountPairs(words);coutresultendl;return0;}