当前位置：首页 > news >正文

【每日一题】LeetCode 2306.公司命名（位运算、数组、哈希表、字符串、枚举）

news 来源：原创 2024/9/27 7:24:37

【每日一题】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^4
1 <= ideas[i].length <= 10
ideas[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;// 外层循环遍历选择ideaAfor (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++;}}}// 由于每一对可以交换两次，所以最终结果需要乘以2return 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}
}