Hard
题目描述
给你一个字符串数组 ideas，表示在公司命名过程中使用的名字列表。公司的命名规则如下：
- 从
ideas中选择 2 个不同的名字，称为ideaA和ideaB。 - 交换
ideaA和ideaB的首字母。 - 如果得到的两个新名字都不在原始的
ideas中，那么ideaA ideaB（用空格分隔ideaA和ideaB连接起来）是一个有效的公司名字。 - 否则，这不是一个有效的名字。
返回不同的有效名字的数目。
示例 1：
输入：ideas = ["coffee","donuts","time","toffee"]
输出：6
解释：下面的选择是有效的：
- ("coffee", "donuts")：产生的公司名字是 "doffee conuts"。
- ("donuts", "coffee")：产生的公司名字是 "conuts doffee"。
- ("donuts", "time")：产生的公司名字是 "tonuts dime"。
- ("donuts", "toffee")：产生的公司名字是 "tonuts doffee"。
- ("time", "donuts")：产生的公司名字是 "dime tonuts"。
- ("toffee", "donuts")：产生的公司名字是 "doffee tonuts"。
因此，总共有 6 个不同的公司名字。
下面是一些无效选择的例子：
- ("coffee", "time")：交换后得到 "toffee"，已存在于原数组中。
- ("time", "toffee")：交换后两个名字都保持不变，且都存在于原数组中。
- ("coffee", "toffee")：交换后得到的两个名字都已存在于原数组中。
示例 2：
输入：ideas = ["lack","back"]
输出：0
解释：不存在有效的选择，因此返回 0。
提示：
2 <= ideas.length <= 5 * 10^41 <= ideas[i].length <= 10ideas[i]由小写英文字母组成ideas中的所有字符串都是唯一的
解题思路
这道题的关键在于理解什么情况下两个单词可以形成有效的公司名字。
核心思路： 当我们选择两个单词 A 和 B，交换它们的首字母后，得到 A’ 和 B’。只有当 A’ 和 B’ 都不在原数组中时，这对单词才是有效的。
分组策略： 我们可以按照单词的后缀（除首字母外的部分）对单词进行分组。例如：
- “coffee” 和 “toffee” 都有后缀 “offee”
- “donuts” 有后缀 “onuts”
- “time” 有后缀 “ime”
对于同一组内的两个单词，交换首字母后仍然会产生原组内存在的单词，因此同组内的配对都是无效的。
计算有效配对： 只有不同组之间的单词才可能形成有效配对。对于两个不同的组 G1 和 G2，我们需要统计：
- 在 G1 中以字母 x 开头的单词数量
- 在 G2 中以字母 y 开头的单词数量
- 当 G2 中不包含以字母 x 开头的单词，且 G1 中不包含以字母 y 开头的单词时，这些单词可以相互配对
算法步骤：
- 按后缀对单词分组，同时记录每组中各首字母的出现次数
- 对于每对不同的组，计算它们之间的有效配对数
- 统计总的有效配对数（注意每对单词可以产生2个有效的公司名字）
代码实现
class Solution {
public:
long long distinctNames(vector<string>& ideas) {
unordered_map<string, unordered_map<char, int>> groups;
// 按后缀分组，统计每组中各首字母的数量
for (const string& idea : ideas) {
string suffix = idea.substr(1);
groups[suffix][idea[0]]++;
}
long long result = 0;
auto groupList = vector<pair<string, unordered_map<char, int>>>(groups.begin(), groups.end());
// 计算不同组之间的有效配对
for (int i = 0; i < groupList.size(); i++) {
for (int j = i + 1; j < groupList.size(); j++) {
const auto& group1 = groupList[i].second;
const auto& group2 = groupList[j].second;
// 统计每组中不与另一组冲突的首字母的单词数量
int count1 = 0, count2 = 0;
for (const auto& [ch, cnt] : group1) {
if (group2.find(ch) == group2.end()) {
count1 += cnt;
}
}
for (const auto& [ch, cnt] : group2) {
if (group1.find(ch) == group1.end()) {
count2 += cnt;
}
}
// 每对单词可以产生2个公司名字（A+B和B+A）
result += 2LL * count1 * count2;
}
}
return result;
}
};
class Solution:
def distinctNames(self, ideas: List[str]) -> int:
from collections import defaultdict
# 按后缀分组，统计每组中各首字母的数量
groups = defaultdict(lambda: defaultdict(int))
for idea in ideas:
suffix = idea[1:]
groups[suffix][idea[0]] += 1
result = 0
group_list = list(groups.items())
# 计算不同组之间的有效配对
for i in range(len(group_list)):
for j in range(i + 1, len(group_list)):
_, group1 = group_list[i]
_, group2 = group_list[j]
# 统计每组中不与另一组冲突的首字母的单词数量
count1 = sum(cnt for ch, cnt in group1.items() if ch not in group2)
count2 = sum(cnt for ch, cnt in group2.items() if ch not in group1)
# 每对单词可以产生2个公司名字（A+B和B+A）
result += 2 * count1 * count2
return result
public class Solution {
public long DistinctNames(string[] ideas) {
var groups = new Dictionary<string, Dictionary<char, int>>();
// 按后缀分组，统计每组中各首字母的数量
foreach (var idea in ideas) {
string suffix = idea.Substring(1);
if (!groups.ContainsKey(suffix)) {
groups[suffix] = new Dictionary<char, int>();
}
if (!groups[suffix].ContainsKey(idea[0])) {
groups[suffix][idea[0]] = 0;
}
groups[suffix][idea[0]]++;
}
long result = 0;
var groupList = groups.ToList();
// 计算不同组之间的有效配对
for (int i = 0; i < groupList.Count; i++) {
for (int j = i + 1; j < groupList.Count; j++) {
var group1 = groupList[i].Value;
var group2 = groupList[j].Value;
// 统计每组中不与另一组冲突的首字母的单词数量
int count1 = 0, count2 = 0;
foreach (var kvp in group1) {
if (!group2.ContainsKey(kvp.Key)) {
count1 += kvp.Value;
}
}
foreach (var kvp in group2) {
if (!group1.ContainsKey(kvp.Key)) {
count2 += kvp.Value;
}
}
// 每对单词可以产生2个公司名字（A+B和B+A）
result += 2L * count1 * count2;
}
}
return result;
}
}
var distinctNames = function(ideas) {
const groups = new Map();
// 按后缀分组，统计每组中各首字母的数量
for (const idea of ideas) {
const suffix = idea.slice(1);
if (!groups.has(suffix)) {
groups.set(suffix, new Map());
}
const group = groups.get(suffix);
const firstChar = idea[0];
group.set(firstChar, (group.get(firstChar) || 0) + 1);
}
let result = 0;
const groupList = Array.from(groups.entries());
// 计算不同组之间的有效配对
for (let i = 0; i < groupList.length; i++) {
for (let j = i + 1; j < groupList.length; j++) {
const group1 = groupList[i][1];
const group2 = groupList[j][1];
// 统计每组中不与另一组冲突的首字母的单词数量
let count1 = 0, count2 = 0;
for (const [ch, cnt] of group1) {
if (!group2.has(ch)) {
count1 += cnt;
}
}
for (const [ch, cnt] of group2) {
if (!group1.has(ch)) {
count2 += cnt;
}
}
// 每对单词可以产生2个公司名字（A+B和B+A）
result += 2 * count1 * count2;
}
}
return result;
};
复杂度分析
| 复杂度类型 | 值 |
|---|---|
| 时间复杂度 | O(n * L + G²) |
| 空间复杂度 | O(n * L) |
其中：
- n 是 ideas 数组的长度
- L 是字符串的平均长度
- G 是不同后缀的数量（最多为 n）
时间复杂度分析：
- 分组阶段：O(n * L)，需要遍历所有字符串并提取后缀
- 计算配对阶段：O(G² * 26)，需要遍历所有组对，每次检查26个字母
空间复杂度分析：
- 存储分组信息需要 O(n * L) 的空间