318. Maximum word length product

318. Maximum word length product

Original title link ：https://leetcode.cn/problems/maximum-product-of-word-lengths/

Here's an array of strings words , Find out and return to length(words[i]) * length(words[j]) The maximum of , And these two words don't have a common letter . If there are no such two words , return 0 .

Example 1：

Input ：words = [“abcw”,“baz”,“foo”,“bar”,“xtfn”,“abcdef”]
Output ：16
explain ： These two words are “abcw”, “xtfn”.
Example 2：

Input ：words = [“a”,“ab”,“abc”,“d”,“cd”,“bcd”,“abcd”]
Output ：4
explain ： These two words are “ab”, “cd”.
Example 3：

Input ：words = [“a”,“aa”,“aaa”,“aaaa”]
Output ：0
explain ： There are no such two words .

Tips ：

2 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] Only lowercase letters

Their thinking ：

First, remove each string in the array , Use set Gather to get rid of the heavy , The result of de duplication is a set , Convert to string , As in the dictionary key,value Is the length of the string without weight removal . Judge whether the current string intersects with the string in the dictionary , When the length of the de duplicated string is not equal to that of the non duplicated string , Specifically , Small after weight removal , This is the time to judge .

Code implementation ：

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        from collections import defaultdict
        words_dict = defaultdict(int)
        ans = 0

        for word in words:
            #  Use sets to remove duplicates word
            word_set = set(word)
            #  Convert to string , Used as a dictionary key, think set Not as key, Length as value
            #  Put the de duplicated string into the dictionary , Used to compare whether two strings coincide 
            word_set_str = ''.join(word_set)

            #  If the length of the de duplicated character in the dictionary is smaller than the current character length , Then there may be the maximum value required by the problem 
            if words_dict[word_set_str] < len(word):
                #  Ergodic dictionary 
                for key in words_dict:
                    #  Judge whether there is an intersection between the string in the dictionary and the current de duplicated string 
                    #  There is no intersection , In line with the question , Update Max 
                    if not set(key) & word_set:
                        ans = max(ans, len(word) * words_dict[key])
                #  Update Dictionary 
                words_dict[word_set_str] = len(word)

        return ans

reference ：
https://leetcode.cn/problems/maximum-product-of-word-lengths/solution/pythonjavajavascriptgo-zi-zhi-hashable-s-tuxj/