feat: $2306

robot · robot · commit 831123edabb1 · 2022-06-18T15:51:22.000+08:00
diff --git a/README.md b/README.md
@@ -536,7 +536,8 @@ leetcode 题解，记录自己的 leetcode 解题之路。
 - [2030. 含特定字母的最小子序列](./problems/2030.smallest-k-length-subsequence-with-occurrences-of-a-letter.md)
 - [2102. 序列顺序查询](./problems/2102.sequentially-ordinal-rank-tracker.md)
 - [2209. 用地毯覆盖后的最少白色砖块](./problems/2209.minimum-white-tiles-after-covering-with-carpets.md) 👍
-- [2281.sum-of-total-strength-of-wizards](./problems/2281.sum-of-total-strength-of-wizards.md)
+- [2281. 巫师的总力量和](./problems/2281.sum-of-total-strength-of-wizards.md)
+- [2306. 公司命名](./problems/2306.naming-a-company.md) 枚举优化好题
 - [5999. 统计数组中好三元组数目](./problems/5999.count-good-triplets-in-an-array.md) 👍
 
 ## :trident: &nbsp;anki 卡片
diff --git a/SUMMARY.md b/SUMMARY.md
@@ -352,6 +352,7 @@
   - [2102. 序列顺序查询](./problems/2102.sequentially-ordinal-rank-tracker.md)
   - [2209. 用地毯覆盖后的最少白色砖块](./problems/2209.minimum-white-tiles-after-covering-with-carpets.md)
   - [2281.sum-of-total-strength-of-wizards](./problems/2281.sum-of-total-strength-of-wizards.md)
+  - [2306. 公司命名](./problems/2306.naming-a-company.md) 枚举优化好题
   - [5999. 统计数组中好三元组数目](./problems/5999.count-good-triplets-in-an-array.md) 👍
 
 - [后序](epilogue.md)
diff --git a/problems/2306.naming-a-company.md b/problems/2306.naming-a-company.md
@@ -0,0 +1,186 @@
+## 题目地址(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 两个集合的笛卡尔。
+
+2. 组合后哪些是无效，哪些是有效的？
+
+根据题目要求，应该是**得到的两个新名字至少有一个在 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://tva1.sinaimg.cn/large/007S8ZIlly1gfcuzagjalj30p00dwabs.jpg)
