leetcode：6094. Company name [group enumeration + cannot repeat set intersection + product Cartesian product (repeat indicates length)]

analysis

Start with the first letter key, The following letter is value（ To get a set Come out and save ）
Then different initials are divided into different groups
And then through product The cartesian product , Consider different groups , Only consider the case that the first letter selected is less than the second letter （ The opposite can happen *2 Handle , The same does not conform to ）
Then there are two of these two groups set, If set There is the same in , Obviously, this value cannot be obtained , Otherwise, it will be exchanged and get in another set in
So the contribution of the two groups at this time is (len(s1) - len(s1 & s2)) * (len(s2) - len(s1 & s2)) * 2
Be careful py Medium set It's disorder hashtable It's done , So all the additions, deletions, modifications and checks are o1, So generally speaking, this sentence is spelled as on Complexity
So the total complexity is 26 ** 2 * on complacent

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))) #  The length is 2 The Cartesian product of 
        
        #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

summary

Split the title
Group according to the first letter
Different groups of words must not be followed by the same
Then remember to take 2 that will do （ In this way, we only need to consider the case that the former is less than the latter ）