-
发表于 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
- LC 题目链接
-