最大单词长度乘积

标签: 位运算 数组 字符串

难度: Medium

给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。

示例 1:

输入: words = ["abcw","baz","foo","bar","fxyz","abcdef"]
输出: 16 
解释: 这两个单词为 "abcw", "fxyz"。它们不包含相同字符，且长度的乘积最大。

示例 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] 仅包含小写字母

注意：本题与主站 318 题相同：https://leetcode-cn.com/problems/maximum-product-of-word-lengths/

Submission

运行时间: 106 ms

内存: 16.4 MB

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        ###集合+位运算
        dic={}
        for word in words:
            w=0
            for ww in word:
                u=ord(ww)-ord('a')
                w|=1<<u
            if w not in dic or dic[w]<len(word):
                dic[w]=len(word)
        res=0
        for a in dic:
            for b in dic:
                if a&b==0:
                    res=max(res,dic[a]*dic[b])
        return res

Explain

本题解采用了位运算和哈希表的方法来处理问题。首先，对于每个字符串，使用一个整数来表示其字符集，其中每个位的二进制表示是否包含从'a'到'z'的各个字符。这是通过遍历单词的每个字符，计算其相对于'a'的偏移，并将对应的位设置为1来完成的。然后，这个整数和单词的长度被存储在字典中，其中键是整数（字符集的位表示），值是对应的最长单词的长度。最后，对于字典中的每一对整数，如果两个整数的按位与为0（表示没有公共字符），则计算它们对应长度的乘积，并更新结果。

时间复杂度: O(n * L + k^2)

空间复杂度: O(k)

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        ### 集合+位运算
        dic = {} # 字典用于存储每个唯一字符集的最长单词长度
        for word in words:
            w = 0  # 用于存储单词字符集的整数表示
            for ww in word:
                u = ord(ww) - ord('a') # 计算字符相对于'a'的偏移
                w |= 1 << u  # 设置对应位
            if w not in dic or dic[w] < len(word): # 更新字典
                dic[w] = len(word)
        res = 0 # 用于存储最大乘积
        for a in dic:
            for b in dic:
                if a & b == 0: # 检查无共同字符
                    res = max(res, dic[a] * dic[b]) # 计算并更新最大乘积
        return res

Explore

在本题解中，使用一个整数的每一位来表示一个字符是否存在，总共有26个英文字母，因此至少需要26位来表示所有可能的字符。由于整数类型通常至少有32位，完全足够表示所有英文小写字母。这种方法中，每个位独立代表一个字符，不同字符的组合不会影响其他位，因此不存在不同字符组合会导致表示冲突的问题。例如，字符'a'对应整数的第0位，字符'b'对应第1位，即使在不同单词中字符的组合不同，它们在整数中的表示也不会互相影响。

在解决这个问题的目标是找到没有共同字符的两个单词，它们长度的乘积最大。如果两个单词具有相同的字符集，那么它们之间无法形成有效的乘积对（因为它们的按位与不为0）。因此，对于具有相同字符集的单词，只保留最长的单词可以简化问题的复杂度，因为只有最长的单词才可能与其他字符集的单词组合形成最大的乘积。存储所有单词长度将增加不必要的空间和计算复杂度，而不会影响最终结果。

是的，这种方法确实考虑了所有可能的字符集合组合。通过将每个单词的字符集转换为整数表示，并将这些整数作为字典的键，我们可以确保每个独特的字符集都被考虑到。在比较过程中，我们检查所有可能的整数对，如果两个整数的按位与为0，意味着这两个整数代表的字符集没有交集，即对应的单词没有公共字符。这样的方法系统地覆盖了所有独特字符集的组合，确保不遗漏任何一个可能的乘积对。