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"] 会预处理为:

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

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

暴力法代码:

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:


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)$

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~

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

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

最后更新于