1.题目基本信息

1.1.题目描述

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

1.2.题目地址

https://leetcode.cn/problems/maximum-product-of-word-lengths/description/

2.解题方法

2.1.解题思路

位运算。使用二进制集合的交集判断单词字符串是否有公共字母

2.2.解题步骤

第一步，计算所有单词的二进制掩码（本质就是构建各个单词的字符集合）

第二步，遍历单词组合对。求无公共字母的单词对的最大长度乘积

3.解题代码

python代码

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        # 思路：位运算。使用二进制集合的交集判断单词字符串是否有公共字母
        n = len(words)
        # 第一步，计算所有单词的二进制掩码（本质就是构建各个单词的字符集合）
        masks = [0] * n
        for i, word in enumerate(words):
            for c in word:
                masks[i] |= (1 << (ord(c) - ord('a')))
        # 第二步，遍历单词组合对。求无公共字母的单词对的最大长度乘积
        result = 0
        for i in range(n):
            for j in range(i + 1, n):
                if masks[i] & masks[j] == 0:
                    result = max(result, len(words[i]) * len(words[j]))
        return result

4.执行结果