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
}

复制