【位运算】力扣318：最大单词长度乘积

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

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

示例2：

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

为了得到最大单词长度乘积，朴素的做法是，遍历字符串数组 words 中的每一对单词，判断这一对单词是否有公共字母，如果没有公共字母，则用这一对单词的长度乘积更新最大单词长度乘积。
用 n 表示数组 words 的长度，用 \(l_i\) 表示单词 words[i] 的长度，其中 0 ≤ i < n，则上述做法需要遍历字符串数组 words 中的每一对单词，对于下标为 i 和 j 的单词，其中 i < j，需要 O(\(l_i\) × \(l_j\)) 的时间判断是否有公共字母和计算长度乘积。因此上述做法的时间复杂度是 O(\(\sum_{0 \le i < j < n} l_i × l_j\))，该时间复杂度高于 O(\(n^2\))。

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        n = len(words)
        maxProd = 0
        for i in range(n - 1):
            for j in range(i + 1, n):
                for word in words[i]:
                    if word in words[j]:
                        break
                else: # Don't find the word
                    prod = len(words[i]) * len(words[j])
                    if maxProd < prod:
                        maxProd = prod
        return maxProd

可以用位运算来暴力破解

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        maxProd = 0
        for w1 in words:
            for w2 in words:
                # set(w1) & set(w2) 为 False 说明两个单词不含有公共字母
                if not (set(w1) & set(w2)):
                   maxProd = max(maxProd, len(w1) * len(w2))
        return maxProd

缩减为一行代码：注意生成器表达式（Generator expression）必须括起来

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        return max([len(w1) * len(w2) for w1 in words for w2 in words if not set(w1) & set(w2)] or [0])

可以看出第二种方法对每个单词都多遍历了一个（自身），所以时间浪费很多。

位运算
如果可以将判断两个单词是否有公共字母的时间复杂度降低到 O(1)，则可以将总时间复杂度降低到 O(\(n^2\))。
对于：abc，bac，cba...这样字符串其实都是一个意思，是否能找到一样东西可以代表它们？
可以为每个字母串建立一个长度为 26 的二进制数字，每个位置表示是否存在该字母。如果两个字母串含有重复数字，那它们的二进制表示的【按位与】不为 0。
a->1，b->10 ... ab->11，ba->11
由于单词只包含小写字母，共有 26 个小写字母，因此可以使用位掩码的【最低 26 位】分别表示每个字母是否在这个单词中出现。将 a 到 z 分别记为第 0 个字母到第 25 个字母，则当且仅当第 i 个字母在这个单词中，位掩码的从低到高（从右到左）的第 i 位是 1，其中 0 ≤ i ≤ 25。
用数组 masks 记录每个单词的位掩码表示。计算数组 masks 之后，判断第 i 个单词和第 j 个单词是否有公共字母可以通过判断 masks[i] & masks[j] 是否等于 0 实现，当且仅当 masks[i] & masks[j] == 0 时第 i 个单词和第 j 个单词没有公共字母，此时使用这两个单词的长度乘积更新最大单词长度乘积。

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        n = len(words)
        masks = [0] * n
        # 用位运算表示单词word
        for i in range(n):
            for alphabet in words[i]:
                masks[i] |= 1 << (ord(alphabet) - 97)
        maxProd = 0
        for i in range(n - 1):
            for j in range(i, n):
                if not masks[i] & masks[j]: # masks[i] & masks[j] == 0
                    maxProd = max(maxProd, len(words[i]) * len(words[j]))
        return maxProd

代码合并

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        masks = [reduce(lambda a, b: a | (1 << (ord(b) - ord('a'))), word, 0) for word in words]
        return max((len(x[1]) * len(y[1]) for x, y in product(zip(masks, words), repeat=2) if x[0] & y[0] == 0), default=0)

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/maximum-product-of-word-lengths/solution/zui-da-dan-ci-chang-du-cheng-ji-by-leetc-lym9/

时间复杂度：O(L + n^2)，其中 L 是数组 words 中的全部单词长度之和，n 是数组 words 的长度。预处理每个单词的位掩码需要遍历全部单词的全部字母，时间复杂度是 O(L)；然后需要使用两重循环遍历位掩码数组 masks 计算最大单词长度乘积，时间复杂度是 O(n^2)，因此总时间复杂度是 O(L + n^2)。
空间复杂度：O(n)，其中 n 是数组 words 的长度。需要创建长度为 n 的位掩码数组 masks。

位运算优化：
位运算方法中，每个单词的二进制都被记录了，但是 比如 abc、aaabc包含的字母相同，只是字母的出现次数和单词长度不同，因此这两个单词的位掩码表示也相同，只需要记录长的单词即可。
可以建立一个哈希表来记录每个位掩码对应的最大单词长度，然后遍历哈希表中的每一对位掩码。由于每个单词的位掩码都不等于 0，任何一个不等于 0 的数和自身做按位与运算的结果一定不等于 0，因此当一对位掩码的按位与运算等于 0 时，这两个位掩码一定是不同的，对应的单词也一定是不同的。

from collections import defaultdict
class Solution:
    def maxProduct(self, words: List[str]) -> int:
        lookup = defaultdict(int)
        for i in range(len(words)):
            mask = 0
            for alp in words[i]:
                mask |= 1 << (ord(alp) - 97)
            lookup[mask] = max(lookup[mask], len(words[i]))
        #print(lookup)
        return max([lookup[x] * lookup[y] for x in lookup for y in lookup if not x & y] or [0])

代码合并

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        masks = defaultdict(int)
        for word in words:
            mask = reduce(lambda a, b: a | (1 << (ord(b) - ord('a'))), word, 0)
            masks[mask] = max(masks[mask], len(word))
        return max((masks[x] * masks[y] for x, y in product(masks, repeat=2) if x & y == 0), default=0)

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/maximum-product-of-word-lengths/solution/zui-da-dan-ci-chang-du-cheng-ji-by-leetc-lym9/

时间复杂度：O(L + n^2)，其中 L 是数组 words 中的全部单词长度之和，n 是数组 words 的长度。预处理每个单词的位掩码并将位掩码对应的最大单词长度存入哈希表需要遍历全部单词的全部字母，时间复杂度是 O(L)，然后需要使用两重循环遍历哈希表计算最大单词长度乘积，时间复杂度是 O(n^2)，因此总时间复杂度是 O(L + n^2)。
空间复杂度：O(n)，其中 n 是数组 words 的长度。需要创建哈希表记录每个位掩码对应的最大单词长度，哈希表中的记录数量不会超过 n。