[数据结构与算法]318. 最大单词长度乘积

318. 最大单词长度乘积

原始题目链接：https://leetcode.cn/problems/maximum-product-of-word-lengths/

给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。

示例 1：

输入：words = [“abcw”,“baz”,“foo”,“bar”,“xtfn”,“abcdef”]
输出：16
解释：这两个单词为 “abcw”, “xtfn”。
示例 2：

输入：words = [“a”,“ab”,“abc”,“d”,“cd”,“bcd”,“abcd”]
输出：4
解释：这两个单词为 “ab”, “cd”。
示例 3：

输入：words = [“a”,“aa”,“aaa”,“aaaa”]
输出：0
解释：不存在这样的两个单词。

提示：

2 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] 仅包含小写字母

解题思路：

先去重数组中每个字符串，使用set集合去重，去重后的结果是个集合，转换成字符串，当做字典中的key，value是没去重的字符串的长度。判断当前字符串和字典中的字符串是否有交集，当去重后的字符串和没去重的字符串的长度不相等的时候，具体说是，去重后的小，这个时候判断。

代码实现：

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

        for word in words:
            # 使用集合去重word
            word_set = set(word)
            # 转换成字符串，用做字典的key，以为set不能当做key，长度作为value
            # 将去重后的字符串放进字典中，用于比较两个字符串是否有重合
            word_set_str = ''.join(word_set)

            # 如果字典中的去重后的字符长度比当前字符长度小，则有可能存在题目要求的最大值
            if words_dict[word_set_str] < len(word):
                # 遍历字典
                for key in words_dict:
                    # 判断字典中的字符串和当前去重后的字符串是否有交集
                    # 没有交集，符合题意，更新最大值
                    if not set(key) & word_set:
                        ans = max(ans, len(word) * words_dict[key])
                # 更新字典
                words_dict[word_set_str] = len(word)

        return ans

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