公司命名
难度:
标签:
题目描述
代码结果
运行时间: 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来获取最终的公司名数量?
▷🦆
解法中提到了遍历所有可能的两个不同首字母组的组合,这里的组合是如何实现的?具体使用了哪种算法或方法?
▷🦆
在实际的算法实现中,如何确保生成的新名字确实不在原始的`ideas`列表中?
▷