公司命名

标签: 位运算 数组 哈希表 字符串 枚举

难度: Hard

给你一个字符串数组 ideas 表示在公司命名过程中使用的名字列表。公司命名流程如下：

  1. 从 ideas 中选择 2 个 不同 名字，称为 ideaA 和 ideaB 。
  2. 交换 ideaA 和 ideaB 的首字母。
  3. 如果得到的两个新名字 都 不在 ideas 中，那么 ideaA ideaB（串联 ideaA 和 ideaB ，中间用一个空格分隔）是一个有效的公司名字。
  4. 否则，不是一个有效的名字。

返回 不同 且有效的公司名字的数目。

示例 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 中的所有字符串 互不相同

Submission

运行时间: 152 ms

内存: 28.1 MB

class Solution:
    def distinctNames(self, ideas: List[str]) -> int:
        groups = defaultdict(set)
        for idea in ideas:
            groups[idea[0]].add(idea[1:])
        ans = 0
        for x, y in combinations(groups.values(), 2):
            m = len(x&y)
            ans += (len(x) - m) * (len(y) - m)
        return ans*2

Explain

此题解首先使用一个defaultdict将所有名字按首字母分类存储，其中键是首字母，值是剩余部分的集合。然后，它采用组合的方法遍历所有可能的两个不同首字母组的组合。对于每一对组合，计算两组中相同后缀的数量m。有效的公司名字数目可以通过计算每个组中排除共同后缀后的元素数相乘得到，即(len(x) - m) * (len(y) - m)，这是因为这些后缀与另一组的任何不同后缀结合都会生成不在原列表中的新名字。最后，由于每一对名字可以互换，所以总数乘以2得到结果。

时间复杂度: O(n + c^2 * min(|x|, |y|))

空间复杂度: O(n)

class Solution:
    def distinctNames(self, ideas: List[str]) -> int:
        groups = defaultdict(set)  # 使用defaultdict来存储每个首字母对应的后缀集合
        for idea in ideas:  # 遍历所有idea，分组存储
            groups[idea[0]].add(idea[1:])
        ans = 0  # 初始化有效公司名字的计数器
        for x, y in combinations(groups.values(), 2):  # 遍历所有首字母组合
            m = len(x & y)  # 计算两个集合中相同后缀的数量
            ans += (len(x) - m) * (len(y) - m)  # 计算有效的公司名字数量
        return ans * 2  # 因为每对名字可以互换，所以结果要乘以2

Explore

通过将名字按首字母分类存储，可以有效地将问题分解成较小的子问题。每个分类存储的集合仅包含具有相同首字母的后缀，这样在计算可能的新公司名字时，只需考虑不同首字母的集合之间的组合。这种方法避免了将整个名单进行全面的两两比较，大幅度降低了计算复杂度，因为我们只对有限的首字母组合进行操作，而不是对每个名字进行单独处理。

由于每一对不同首字母组合的名字可以互换首字母生成新的名字，例如从首字母组合 ('a', 'b') 生成的名字和从 ('b', 'a') 生成的名字是不同的，但都是有效的。因此，对于每一对首字母组合，我们实际上可以生成两倍的有效公司名字数量。最后将结果乘以2是为了包含这种首字母的互换可能性。

在题解中，使用了Python的`combinations`函数，该函数是`itertools`模块的一部分，用于生成所有可能的k元组组合，这里k为2。当我们调用`combinations(groups.values(), 2)`时，它会从字典`groups`的值集合（即不同首字母的后缀集）中产生所有可能的两个不同集合的组合。这种方法自动地处理组合的生成，确保每一对组合仅被考虑一次，从而有效率地枚举了所有首字母的可能组合。

算法通过确保只组合具有不同首字母但相同后缀的名字来生成新名字。具体地，对于两个不同的首字母组，算法计算两组中相同的后缀数量（集合交集的大小），然后计算每个组中独有的后缀数量（即总数减去交集的大小）。新的名字组合是通过将一个组的首字母与另一组的独有后缀组合而成的，反之亦然。由于原始的`ideas`列表中的名字都是同首字母的完整名字，这种方式自然地确保了任何新生成的名字（由不同首字母与独有后缀组合而成）不会出现在原始列表中。