Medium
题目描述
给你一个由 n 个字符串组成的数组 words。每个字符串的长度为 m，只包含小写英文字母。
如果可以对两个字符串 s 和 t 执行以下操作任意次数（可能为 0 次），使得 s 和 t 变得相等，则称这两个字符串相似：
- 选择 s 或 t 中的一个
- 将选择的字符串中的每个字母替换为字母表中的下一个字母（循环）。字母 ‘z’ 的下一个字母是 ‘a’。
计算满足以下条件的索引对 (i, j) 的数量：
- i < j
- words[i] 和 words[j] 相似
返回表示此类对数的整数。
示例 1：
输入：words = [“fusion”,“layout”]
输出：1
解释：
words[0] = “fusion” 和 words[1] = “layout” 相似，因为我们可以对 “fusion” 执行 6 次操作。字符串 “fusion” 的变化如下：
- “fusion”
- “gvtjpo”
- “hwukqp”
- “ixvlrq”
- “jywmsr”
- “kzxnts”
- “layout”
示例 2：
输入：words = [“ab”,“aa”,“za”,“aa”]
输出：2
解释：
words[0] = “ab” 和 words[2] = “za” 相似。words[1] = “aa” 和 words[3] = “aa” 相似。
约束条件：
- 1 <= n == words.length <= 10^5
- 1 <= m == words[i].length <= 10^5
- 1 <= n * m <= 10^5
- words[i] 只包含小写英文字母
提示：
- 如果两个字符串的相邻字符之间的差值（mod 26）相同，则它们相似；通过将每个字符串的第一个字符移位到 ‘a’ 来标准化每个字符串
- 为每个标准化字符串计算一个可哈希的键，表示其相对字符差异
- 使用映射来计算有多少字符串共享相同的标准化键
解题思路
解题思路
这道题的核心在于理解什么是"相似"的字符串。两个字符串相似，意味着它们可以通过凯撒密码的方式互相转换。
关键观察
凯撒密码的本质：如果字符串 A 可以通过 k 次移位变成字符串 B，那么 A 和 B 中对应位置字符的差值都是 k（mod 26）。
标准化策略：我们可以将每个字符串标准化，使其第一个字符变为 ‘a’，这样相似的字符串会有相同的标准化形式。
差值序列：对于标准化后的字符串，我们可以计算相邻字符之间的差值序列。相似的字符串会有相同的差值序列。
算法步骤
- 对每个字符串进行标准化：将第一个字符移位到 ‘a’，其他字符按相同偏移量移位
- 计算标准化后字符串的特征（可以是差值序列或标准化字符串本身）
- 使用哈希表统计具有相同特征的字符串数量
- 对于每组有 count 个相似字符串的组，贡献的配对数为 count * (count - 1) / 2
这种方法的时间复杂度为 O(n * m)，空间复杂度为 O(n * m)，其中 n 是字符串数量，m 是字符串长度。
代码实现
class Solution {
public:
long long countPairs(vector<string>& words) {
unordered_map<string, int> count;
for (const string& word : words) {
string normalized = normalize(word);
count[normalized]++;
}
long long result = 0;
for (const auto& pair : count) {
long long c = pair.second;
result += c * (c - 1) / 2;
}
return result;
}
private:
string normalize(const string& word) {
if (word.empty()) return word;
int shift = word[0] - 'a';
string normalized;
for (char c : word) {
int newChar = c - 'a' - shift;
if (newChar < 0) newChar += 26;
normalized += (char)('a' + newChar);
}
return normalized;
}
};
class Solution:
def countPairs(self, words: List[str]) -> int:
from collections import defaultdict
count = defaultdict(int)
for word in words:
normalized = self.normalize(word)
count[normalized] += 1
result = 0
for c in count.values():
result += c * (c - 1) // 2
return result
def normalize(self, word: str) -> str:
if not word:
return word
shift = ord(word[0]) - ord('a')
normalized = []
for c in word:
new_char = (ord(c) - ord('a') - shift) % 26
normalized.append(chr(ord('a') + new_char))
return ''.join(normalized)
public class Solution {
public long CountPairs(string[] words) {
Dictionary<string, int> count = new Dictionary<string, int>();
foreach (string word in words) {
string normalized = Normalize(word);
if (count.ContainsKey(normalized)) {
count[normalized]++;
} else {
count[normalized] = 1;
}
}
long result = 0;
foreach (int c in count.Values) {
result += (long)c * (c - 1) / 2;
}
return result;
}
private string Normalize(string word) {
if (string.IsNullOrEmpty(word)) return word;
int shift = word[0] - 'a';
char[] normalized = new char[word.Length];
for (int i = 0; i < word.Length; i++) {
int newChar = (word[i] - 'a' - shift + 26) % 26;
normalized[i] = (char)('a' + newChar);
}
return new string(normalized);
}
}
var countPairs = function(words) {
function normalize(word) {
if (word.length === 0) return word;
const firstChar = word[0];
const shift = firstChar.charCodeAt(0) - 'a'.charCodeAt(0);
return word.split('').map(char =>
String.fromCharCode((char.charCodeAt(0) - 'a'.charCodeAt(0) - shift + 26) % 26 + 'a'.charCodeAt(0))
).join('');
}
const normalizedMap = new Map();
for (const word of words) {
const normalized = normalize(word);
normalizedMap.set(normalized, (normalizedMap.get(normalized) || 0) + 1);
}
let count = 0;
for (const freq of normalizedMap.values()) {
count += freq * (freq - 1) / 2;
}
return count;
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n × m) | n 是字符串数量，m 是字符串平均长度，需要遍历所有字符串并标准化 |
| 空间复杂度 | O(n × m) | 存储哈希表中的标准化字符串，最坏情况下所有字符串都不同 |