【每日一题】LeetCode 2306.公司命名（位运算、数组、哈希表、字符串、枚举）
【每日一题】LeetCode 2306.公司命名（位运算、数组、哈希表、字符串、枚举）
题目描述
给定一个字符串数组 ideas，表示在公司命名过程中使用的名字列表。我们需要从 ideas 中选择两个不同的名字，称为 ideaA 和 ideaB。然后交换 ideaA 和 ideaB 的首字母。如果交换后得到的两个新名字都不在 ideas 中，那么这两个名字串联起来（中间用一个空格分隔）就是一个有效的公司名字。我们需要返回不同且有效的公司名字的总数。
输入示例
示例 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中的所有字符串互不相同
思路分析
- 遇到困难题，我们先可以尝试暴力枚举，然后再逐步优化！
- 首先，我们将
ideas数组中的所有字符串添加到一个HashSet中，以便快速检查某个字符串是否在ideas中。 - 然后，我们使用两层循环遍历
ideas数组，外层循环选择ideaA，内层循环选择ideaB。 - 对于每一对
ideaA和ideaB，我们交换它们的首字母，得到两个新的名字newIdea1和newIdea2。 - 我们检查这两个新名字是否都不在
ideas中。如果不在，那么这是一个有效的公司名字，计数器count增加。 - 由于每一对
ideaA和ideaB可以交换两次（ideaA与ideaB和ideaB与ideaA），所以我们需要将最终的计数器count乘以 2。
代码实现（暴力枚举）
class Solution {
public long distinctNames(String[] ideas) {
// 将所有名字存入HashSet中，方便快速查找
HashSet<String> set = new HashSet<>();
for (String idea : ideas) {
set.add(idea);
}
// 初始化计数器
long count = 0;
int n = ideas.length;
// 外层循环遍历选择ideaA
for (int i = 0; i < n; i++) {
char firstChar1 = ideas[i].charAt(0); // 获取ideaA的首字母
// 内层循环遍历选择ideaB，从i+1开始避免重复
for (int j = i + 1; j < n; j++) {
char firstChar2 = ideas[j].charAt(0); // 获取ideaB的首字母
// 交换首字母后的新名字
String newIdea1 = firstChar2 + ideas[i].substring(1);
String newIdea2 = firstChar1 + ideas[j].substring(1);
// 如果两个新名字都不在ideas中，那么这是一个有效的公司名字
if (!set.contains(newIdea1) && !set.contains(newIdea2)) {
count++;
}
}
}
// 由于每一对可以交换两次，所以最终结果需要乘以2
return count * 2;
}
}
思路优化
- 我们可以使用一个数组
groups来存储按首字母分组的后缀。 - 遍历
ideas数组，将每个字符串的后缀（去掉首字母的部分）添加到对应的HashSet中。 - 使用两层循环遍历
groups数组，外层循环选择首字母i，内层循环选择首字母j（从i+1开始，避免重复计算）。 - 对于每一对首字母
i和j，我们统计它们共有的后缀数量m。 - 计算可以形成的不同名称的数量，即
(groups[i].size() - m) * (groups[j].size() - m)。 - 由于每一对
ideaA和ideaB可以交换两次（ideaA与ideaB和ideaB与ideaA），所以我们需要将最终的计数器count乘以 2。
代码实现（思路优化）
class Solution {
public long distinctNames(String[] ideas) {
// 开一个set数组存储后缀
HashSet<String>[] groups = new HashSet[26];
for (int i = 0; i < 26; i++) {
groups[i] = new HashSet<>();
}
// 将每个字符串的后缀按照首字母分组
for (String str : ideas) {
groups[str.charAt(0) - 'a'].add(str.substring(1)); // 将后缀加入到对应的 HashSet 中
}
long count = 0;
// 两层循环遍历所有可能的首字母组合
for (int i = 0; i < 26; i++) {
for (int j = i + 1; j < 26; j++) {
int m = 0; // 计数相同后缀的数量
// 统计 i 组和 j 组中相同的后缀数量
for (String s : groups[i]) {
if (groups[j].contains(s)) {
m++;
}
}
// 计算 i 组和 j 组可以形成的不同名称的数量
count += (long)((groups[i].size() - m) * (groups[j].size() - m));
}
}
return count * 2; // 每对组合可以有两种排列，因此乘以 2
}
}