leetcode：6094. 公司命名【分组枚举 + 不能重复用set交集 + product笛卡儿积（repeat表示长度）】

分析

首先以第一个字母为key，后面的字母为value（搞一个set出来存一下）
然后不同的首字母分为不同组
然后通过product笛卡尔积，考虑不同组，只考虑选出的第一个字母小于第二个字母的情况（相反的情况会*2处理，相同不符合）
然后这两组有两个set，如果set中有相同的，那这个值显然时不能取得，否则就会交换后得到在另一个set中
因此此时两个组得贡献就是(len(s1) - len(s1 & s2)) * (len(s2) - len(s1 & s2)) * 2
注意py中的set是无序hashtable做的，所以增删改查都是o1，所以总的来说这句话拼起来就是on复杂度
所以总复杂度是26 ** 2 * on满足的

ac code

class Solution:
    def distinctNames(self, ideas: List[str]) -> int:
        d = defaultdict(set)
        for name in ideas: d[name[0]].add(name[1:])
        print(d)
        print(list(product(d, repeat = 2))) # 长度为2的笛卡儿积
        
        #return sum((len(d[a]) - len(d[a] & d[b])) * (len(d[b]) - len(d[a] & d[b])) * 2 for a, b in product(d, repeat=2) if ord(a) < ord(b))
        ans = 0
        for a, b in product(d, repeat=2): # 26 * 26
            if ord(a) < ord(b): # in order and * 2
                #print(d[a])
                #print(d[b])
                #print(d[a] & d[b])
                # set -> hashtable, & -> o(n)
                ans += (len(d[a]) - len(d[a] & d[b])) * (len(d[b]) - len(d[a] & d[b])) * 2 
        
        return ans

总结

拆分题目
根据首字母分组
不同组的话后面的一定不能取一样的
然后记得乘2即可（这样就只需要考虑前小于后的情况了）