【每日一題】LeetCode 2306.公司命名（位運算、數(shù)組、哈希表、字符串、枚舉）

題目描述

給定一個字符串?dāng)?shù)組 ideas，表示在公司命名過程中使用的名字列表。我們需要從 ideas 中選擇兩個不同的名字，稱為 ideaA 和 ideaB。然后交換 ideaA 和 ideaB 的首字母。如果交換后得到的兩個新名字都不在 ideas 中，那么這兩個名字串聯(lián)起來（中間用一個空格分隔）就是一個有效的公司名字。我們需要返回不同且有效的公司名字的總數(shù)。

輸入示例

示例 1：

輸入：ideas = ["coffee","donuts","time","toffee"]
輸出：6
解釋：下面列出一些有效的選擇方案：
- ("coffee", "donuts")：對應(yīng)的公司名字是 "doffee conuts" 。
- ("donuts", "coffee")：對應(yīng)的公司名字是 "conuts doffee" 。
- ("donuts", "time")：對應(yīng)的公司名字是 "tonuts dime" 。
- ("donuts", "toffee")：對應(yīng)的公司名字是 "tonuts doffee" 。
- ("time", "donuts")：對應(yīng)的公司名字是 "dime tonuts" 。
- ("toffee", "donuts")：對應(yīng)的公司名字是 "doffee tonuts" 。
因此，總共有 6 個不同的公司名字。下面列出一些無效的選擇方案：
- ("coffee", "time")：在原數(shù)組中存在交換后形成的名字 "toffee" 。
- ("time", "toffee")：在原數(shù)組中存在交換后形成的兩個名字。
- ("coffee", "toffee")：在原數(shù)組中存在交換后形成的兩個名字。

示例 2：

輸入：ideas = ["lack","back"]
輸出：0
解釋：不存在有效的選擇方案。因此，返回 0 。

提示

• 2 <= ideas.length <= 5 * 10^4
• 1 <= ideas[i].length <= 10
• ideas[i] 由小寫英文字母組成
• ideas 中的所有字符串互不相同

思路分析

1. 遇到困難題，我們先可以嘗試暴力枚舉，然后再逐步優(yōu)化！
2. 首先，我們將 ideas 數(shù)組中的所有字符串添加到一個 HashSet 中，以便快速檢查某個字符串是否在 ideas 中。
3. 然后，我們使用兩層循環(huán)遍歷 ideas 數(shù)組，外層循環(huán)選擇 ideaA，內(nèi)層循環(huán)選擇 ideaB。
4. 對于每一對 ideaA 和 ideaB，我們交換它們的首字母，得到兩個新的名字 newIdea1 和 newIdea2。
5. 我們檢查這兩個新名字是否都不在 ideas 中。如果不在，那么這是一個有效的公司名字，計數(shù)器 count 增加。
6. 由于每一對 ideaA 和 ideaB 可以交換兩次（ideaA 與 ideaB 和 ideaB 與 ideaA），所以我們需要將最終的計數(shù)器 count 乘以 2。

代碼實現(xiàn)（暴力枚舉）

class Solution {public long distinctNames(String[] ideas) {// 將所有名字存入HashSet中，方便快速查找HashSet<String> set = new HashSet<>();for (String idea : ideas) {set.add(idea);}// 初始化計數(shù)器long count = 0;int n = ideas.length;// 外層循環(huán)遍歷選擇ideaAfor (int i = 0; i < n; i++) {char firstChar1 = ideas[i].charAt(0); // 獲取ideaA的首字母// 內(nèi)層循環(huán)遍歷選擇ideaB，從i+1開始避免重復(fù)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++;}}}// 由于每一對可以交換兩次，所以最終結(jié)果需要乘以2return count * 2;}
}

##思路優(yōu)化

1. 我們可以使用一個數(shù)組 groups 來存儲按首字母分組的后綴。
2. 遍歷 ideas 數(shù)組，將每個字符串的后綴（去掉首字母的部分）添加到對應(yīng)的 HashSet 中。
3. 使用兩層循環(huán)遍歷 groups 數(shù)組，外層循環(huán)選擇首字母 i，內(nèi)層循環(huán)選擇首字母 j（從 i+1 開始，避免重復(fù)計算）。
4. 對于每一對首字母 i 和 j，我們統(tǒng)計它們共有的后綴數(shù)量 m。
5. 計算可以形成的不同名稱的數(shù)量，即 (groups[i].size() - m) * (groups[j].size() - m)。
6. 由于每一對 ideaA 和 ideaB 可以交換兩次（ideaA 與 ideaB 和 ideaB 與 ideaA），所以我們需要將最終的計數(shù)器 count 乘以 2。

##代碼實現(xiàn)（思路優(yōu)化）

class Solution {public long distinctNames(String[] ideas) {// 開一個set數(shù)組存儲后綴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)); // 將后綴加入到對應(yīng)的 HashSet 中}long count = 0;// 兩層循環(huán)遍歷所有可能的首字母組合for (int i = 0; i < 26; i++) {for (int j = i + 1; j < 26; j++) {int m = 0; // 計數(shù)相同后綴的數(shù)量// 統(tǒng)計 i 組和 j 組中相同的后綴數(shù)量for (String s : groups[i]) {if (groups[j].contains(s)) {m++;}}// 計算 i 組和 j 組可以形成的不同名稱的數(shù)量count += (long)((groups[i].size() - m) * (groups[j].size() - m));}}return count * 2; // 每對組合可以有兩種排列，因此乘以 2}
}

效公司名字的總數(shù)。