JZX轻语：简

LeetCode 2306 - 公司命名

发表于2024年09月25日

这种Hard难度的题目，两两比对必然会超时，所以需要找到一种更高效的方法。可以发现以下规律：对于两个首字母x和y，如果以x为首字母存在一个(不包括x的)后缀，其没有以y作为首字母的单词，那么它可以和以y为首字母，且不存在以x为首字母的单词的任一后缀配对。使用哈希表，建立首字母和去掉首字母的后缀的映射，然后统计每个首字母对应的后缀集合。最后，可以使用集合运算，两两枚举首字母（记为x和y），计算两个集合的差集的元素个数（即以x为首字母的集合中，不在y中集合的字母；反之亦然）的乘积，累加即可。

举个例子，假设有以下的ideas：["ab", "ac", "ad", "ae", "ba", "bb", "bc", "bg"]。

则以a为首字母的后缀集合为{"b", "c", "d", "e"}，以b为首字母的后缀集合为{"a", "b", "c", "g"}。

我们可以发现，以a为首字母的后缀集合中，有"d"和"e"两个后缀不在以b为首字母的后缀集合中；以b为首字母的后缀集合中，有"a"和"g"两个后缀不在以a为首字母的后缀集合中，所以共有四个有效的组合：("ad", "ba"), ("ad", "bg"), ("ae", "ba"), ("ae", "bg")。

class Solution:
    def distinctNames(self, ideas: List[str]) -> int:
        ord_a = ord('a')
        first_letter_to_suffix_set = [set() for _ in range(26)]
        for idea in ideas:
            first_letter_to_suffix_set[ord(idea[0]) - ord_a].add(idea[1:])
        ans = 0
        for i in range(26):
            set_i = first_letter_to_suffix_set[i]
            for j in range(i + 1, 26):
                set_j = first_letter_to_suffix_set[j]
                ans += 2 * len(set_i - set_j) * len(set_j - set_i)
        return ans