题目：
给你一个字符串数组 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 * 1041 <= ideas[i].length <= 10ideas[i]由小写英文字母组成ideas中的所有字符串 互不相同
暴力遍历
思路：
枚举所有可能的公司新名字：排列所有 ideas 中的字符串即可
利用哈希表判断 交换首字母后的新名字是否出现在 ideas 中
利用哈希表存储可行的答案，最后哈希表的大小就是答案
代码：
class Solution {
public:
long long distinctNames(vector<string>& ideas) {
// 暴力求解：利用哈希表速度判断
unordered_set<string> setIdeas;
for (int i = 0; i < ideas.size(); i++) {
setIdeas.insert(ideas[i]);
}
unordered_set<string> ans;
for (int i = 0; i < ideas.size(); i++) {
for (int j = 0; j < ideas.size(); j++) {
// ideas[i] 开头， ideas[j]收尾
string a = ideas[i], b = ideas[j];
char temp = a[0];
a[0] = b[0];b[0] = temp;
if (setIdeas.find(a) != setIdeas.end() || setIdeas.find(b) != setIdeas.end()) continue;
string res = a + " " + b;
if (ans.find(res) != ans.end()) continue;
ans.insert(res);
}
}
return ans.size();
}
};
首字母分组
思路：
什么样的一对字符串无法交换首字母？
示例 1 中的 coffee 和 time，虽然这样两个字符串完全不一样，但如果交换了 coffee 和 time 的首字母，会得到字符串 toffee，它在数组 ideas 中，不符合题目要求。
又例如 ideas=[aa,ab,ac,bc,bd,be]，将其分成两组：
第一组：aa,ab,ac。
第二组：bc,bd,be。
其中第一组内的字符串是不能交换首字母的，因为交换后字符串不变，必然在 ideas 中。第二组也同理。
考虑交换第一组的字符串和第二组的字符串，哪些是可以交换首字母的，哪些是不能交换首字母的？
第一组的 ac 无法和第二组的任何字符串交换，因为交换后会得到 bc，它在 ideas 中。
第二组的 bc 无法和第一组的任何字符串交换，因为交换后会得到 ac，它在 ideas 中。
其余字符串对可以交换首字母。
上面的分析立刻引出了如下方法。
按照首字母，把 ideas 分成（至多）26 组字符串。
例如 ideas=[aa,ab,ac,bc,bd,be] 分成如下两组（只记录去掉首字母后的字符串）：
A 组（集合）：{a,b,c}。
B 组（集合）：{c,d,e}。
分组后：
从 A 中选一个不等于 c 的字符串，这有 2 种选法。
从 B 中选一个不等于 c 的字符串，这有 2 种选法。
考虑两个字符串的先后顺序（谁在左谁在右），有 2 种方法。
根据乘法原理，有 2×2×2=8 对符合要求的字符串。
由于无法选交集中的字符串，一般地，从 A 和 B 中可以选出 2 ⋅ (∣A∣−∣A∩B∣) ⋅ (∣B∣−∣A∩B∣)
对符合要求的字符串。其中 ∣S∣ 表示集合 S 的大小。
枚举所有组对，计算上式，累加到答案中。
代码：
class Solution {
public:
long long distinctNames(vector<string>& ideas) {
vector<set<string>> groupIdeas(26);
for (int i = 0; i < ideas.size(); i++) {
string subStr = ideas[i].substr(1);
groupIdeas[ideas[i][0] - 'a'].insert(subStr);
}
long long ans = 0;
for (int i = 0; i < 26; i++) {
for (int j = i + 1; j < 26; j++) {
// 求交集大小
long long m = 0;
for (auto& temp : groupIdeas[i]) {
m += groupIdeas[j].count(temp);
}
ans += (2 * (groupIdeas[i].size() - m) * (groupIdeas[j].size() - m) );
}
}
return ans;
}
};