golang刷letcode：公司命名
golang刷letcode：公司命名
给你一个字符串数组 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 * 104
1 <= ideas[i].length <= 10
ideas[i] 由小写英文字母组成
ideas 中的所有字符串 互不相同
解题思路：
1，首先可以将字符串拆分成两部分：首字母和剩余部分
2，按照剩余部分分组：同一个分组内部的首字母呼唤，必然重复
3，分组间首字母交换，比如groupi和groupj交换，如果groupj中的首字母在groupi中出现过，那么必然重复
4，所以最终结果应该是groupi和groupj中去除公共部分的首字母相互交换。
5，如果按照这个思路实现的话需要求groupi和groupj的组合情况，复杂度是O（n^?2）会超时
6，反过来想，groupi和groupj可以枚举的值都是26个即26^2,我们需要的就是有i无j和无i有j的个数
7，最终只需在一次遍历中统计无i??j的group的个数，cnt[i][j];因为有i无j可以从cnt[j][i]取得
8，在一次遍历中假如在位置i，如果groupi中包含字母a，对于已经遍历过得所有不含a的group的个数就是我们需要的可交换次数
9，由于我们交换后的两个字符串可以互换位置，因此结果需要*2
func distinctNames(ideas []string) (ans int64) {
group := map[string]int{}
for _, s := range ideas {
group[s[1:]] |= 1 << (s[0] - 'a')
}
cnt := [26][26]int{}
for _, mask := range group {
for i := 0; i < 26; i++ {
if mask>>i&1 == 0 {
for j := 0; j < 26; j++ {
if mask>>j&1 > 0 {
cnt[i][j]++
}
}
} else {
for j := 0; j < 26; j++ {
if mask>>j&1 == 0 {
ans += int64(cnt[i][j])
}
}
}
}
}
return ans * 2
}本文分享自 golang算法架构leetcode技术php 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与?腾讯云自媒体分享计划? ，欢迎热爱写作的你一起参与！