# 2306. 公司命名

### 题目地址(2306. 公司命名)

<https://leetcode.cn/problems/naming-a-company/>

### 题目描述

```
给你一个字符串数组 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 中的所有字符串 互不相同
```

### 前置知识

* 枚举
* 笛卡尔积

### 公司

* 暂无

### 思路

为了方便描述，我们称 idea 的首字母为 idea 的前缀，除了首字母的其余部分称为 idea 的后缀。

最简单的暴力思路就是直接模拟。

枚举 ideas， 对于每一个 idea，我们可以将其替换为任意不等于 idea\[0] 的字母 ch。

如果同时满足以下两个条件：

1. ch + idea\[1:] 不在 ideas 中
2. idea\[0] + b 不在 ideas 中。其中 b 指的是和 idea 有公共后缀的后缀。

由于需要枚举前后缀，因此我们可以先用字典预处理出所有的后缀，key 为前缀，value 为后缀，含义为前缀为 key 的后缀集合。

比如 ideas = \["coffee","donuts","time","toffee"] 会预处理为：

```py
c: set(["offee"])
d: set(["onuts"])
t: set(["ime", "offee"])

```

则将其将入到哈希集合中，最后返回哈希集合的大小即可。

暴力法代码：

```py
class Solution:
    def distinctNames(self, ideas: List[str]) -> int:
        ans = set()
        seen = set(ideas)
        starts = collections.defaultdict(list)
        # 预处理出 starts 字典
        for idea in ideas:
            starts[idea[0]].append(idea[1:])

        for idea in ideas:
            for i in range(26):
                ch = chr(i + 97)
                if idea[0] != ch:
                    a = ch + idea[1:]
                    if a not in seen:
                        # 枚举后缀
                        for b in starts[ch]:
                            if idea[0] + b not in seen:
                                ans.add((a, idea[0] + b))
        return len(ans)

```

暴力法会超时，原因在于时间复杂度为 ${O(n^2)}$，代入题目的 $5 \* 10^4$ 的数据规模是通过不了的。如果想通过，需要 $O(nlogn)$ 或者 $O(n)$ 的复杂度才行。

如何优化呢？

我们前面枚举的是 idea， 实际上我们可以只枚举前缀即可。

ideaA 和 ideaB 的前缀组合一共有 $C\_{2}^{26}$ 即 `26 * 25 / 2` 种。

接下来，对于以 ideaA\[0] 开头的后缀列表 set\_x 即 starts\[ideaA\[0]] 和 ideaB\[0] 开头的后缀列表 set\_y 即 starts\[ideaB\[0]]。那么如何组合才能是有效的名字呢?

ideaA\[0] 想和 set\_y 进行组合，有两个问题。

1. 如何组合？

枚举 set\_x 中的后缀，然后枚举 set\_y 两两组合即可，本质上就是 set\_x 和 set\_y 两个集合的笛卡尔。

1. 组合后哪些是无效，哪些是有效的？

根据题目要求，应该是**得到的两个新名字至少有一个在 ideas 中**。其实就是说如果 set\_x 中的后缀 a 在 set\_y 中存在就是无效的。反之 set\_y 中的后缀 b 在 set\_x 中存在也是无效的。

也就是说，set\_x 和 set\_y 的差集和 set\_x 和 set\_y 的补集的笛卡尔积的两倍就是答案。两倍的原因是顺序是重要的，顺序不同会被认为是两个有效名字。

> 需要特别注意的是由于 idea 中没有空格，因此拼接出来的公司名一定不在 ideas 中。

### 关键点

*

### 代码

* 语言支持：Python3

Python3 Code:

```python

class Solution:
    def distinctNames(self, ideas: List[str]) -> int:
        ans = 0
        seen = set(ideas)
        starts = collections.defaultdict(set)

        for idea in ideas:
            starts[idea[0]].add(idea[1:])
        for j in range(25):
            for i in range(j + 1, 26):
                set_x = starts[chr(i + 97)]
                set_y = starts[chr(j + 97)]
                intersections = len(set_x & set_y) # 交集
                ans += 2 * (len(set_x) - intersections) * (len(set_y) - intersections)
        return ans


```

**复杂度分析**

令 n 为数组长度。

* 时间复杂度：$O(n)$
* 空间复杂度：$O(n)$

> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。

力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 48K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://p.ipic.vip/r8633q.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/2306.naming-a-company.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.