leetcode
leetcode 2001 ~ 2050
公司命名

公司命名

难度:

标签:

题目描述

代码结果

运行时间: 152 ms, 内存: 28.1 MB


/*
题目思路:
1. 使用Java Stream API遍历每一对名字。
2. 交换它们的首字母并检查新名字是否在原始数组中。
3. 如果新名字不在数组中,计数器加一。
4. 返回计数器的值。
*/
import java.util.HashSet;
import java.util.Set;
import java.util.stream.IntStream;

public class Solution {
    public int distinctNames(String[] ideas) {
        Set<String> ideaSet = new HashSet<>();
        for (String idea : ideas) {
            ideaSet.add(idea);
        }

        return (int) IntStream.range(0, ideas.length)
                .boxed()
                .flatMap(i -> IntStream.range(i + 1, ideas.length)
                        .mapToObj(j -> new String[]{ideas[i], ideas[j]}))
                .filter(pair -> {
                    String newIdeaA = pair[1].charAt(0) + pair[0].substring(1);
                    String newIdeaB = pair[0].charAt(0) + pair[1].substring(1);
                    return !ideaSet.contains(newIdeaA) && !ideaSet.contains(newIdeaB);
                })
                .count();
    }
}

解释

方法:

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

时间复杂度:

O(n + c^2 * min(|x|, |y|))

空间复杂度:

O(n)

代码细节讲解

🦆
题解中提到了将名字按首字母分类存储,这种分类存储方式是如何帮助减少计算量的?
通过将名字按首字母分类存储,可以有效地将问题分解成较小的子问题。每个分类存储的集合仅包含具有相同首字母的后缀,这样在计算可能的新公司名字时,只需考虑不同首字母的集合之间的组合。这种方法避免了将整个名单进行全面的两两比较,大幅度降低了计算复杂度,因为我们只对有限的首字母组合进行操作,而不是对每个名字进行单独处理。
🦆
为什么在最后需要将结果乘以2来获取最终的公司名数量?
由于每一对不同首字母组合的名字可以互换首字母生成新的名字,例如从首字母组合 ('a', 'b') 生成的名字和从 ('b', 'a') 生成的名字是不同的,但都是有效的。因此,对于每一对首字母组合,我们实际上可以生成两倍的有效公司名字数量。最后将结果乘以2是为了包含这种首字母的互换可能性。
🦆
解法中提到了遍历所有可能的两个不同首字母组的组合,这里的组合是如何实现的?具体使用了哪种算法或方法?
在题解中,使用了Python的`combinations`函数,该函数是`itertools`模块的一部分,用于生成所有可能的k元组组合,这里k为2。当我们调用`combinations(groups.values(), 2)`时,它会从字典`groups`的值集合(即不同首字母的后缀集)中产生所有可能的两个不同集合的组合。这种方法自动地处理组合的生成,确保每一对组合仅被考虑一次,从而有效率地枚举了所有首字母的可能组合。
🦆
在实际的算法实现中,如何确保生成的新名字确实不在原始的`ideas`列表中?
算法通过确保只组合具有不同首字母但相同后缀的名字来生成新名字。具体地,对于两个不同的首字母组,算法计算两组中相同的后缀数量(集合交集的大小),然后计算每个组中独有的后缀数量(即总数减去交集的大小)。新的名字组合是通过将一个组的首字母与另一组的独有后缀组合而成的,反之亦然。由于原始的`ideas`列表中的名字都是同首字母的完整名字,这种方式自然地确保了任何新生成的名字(由不同首字母与独有后缀组合而成)不会出现在原始列表中。

相关问题