How does bit manipulation help solve the Maximum Product of Word Lengths problem?

Bit manipulation allows efficient comparison of words by representing them as bitmasks. This approach enables constant-time checks for overlapping characters, significantly speeding up the solution.

What is the time complexity of the solution?

The time complexity is O(n^2), where n is the number of words, because every pair of words must be checked. However, using bitmasks optimizes the comparison step.

Can the solution handle the upper input limits?

Yes, the solution can handle up to 1000 words, each of up to 1000 characters, by using efficient bitwise operations to minimize redundant calculations.

What is the space complexity of the solution?

The space complexity is O(n), where n is the number of words, as we store a bitmask for each word.

How can the problem be optimized further?

The problem is already optimized by using bitmasks for constant-time word comparison. Further optimizations could focus on reducing the number of word pairs to check, depending on additional constraints.

#318

Medium

auto_awesome数组·string

LeetCode 题解工作台

最大单词长度乘积

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

数组字符串位运算

题目描述

给你一个字符串数组 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] 仅包含小写字母

lightbulb

解题思路

方法一：位运算

题目需要我们找到两个没有公共字母的字符串，使得它们的长度乘积最大。我们可以将每个字符串用一个二进制数 $mask[i]$ 表示，这个二进制数的每一位表示字符串中是否含有某个字母。如果两个字符串没有公共字母，那么这两个字符串对应的二进制数的按位与的结果为 $0$ ，即 $mask[i] \& mask[j] = 0$ 。

我们遍历每个字符串，对于当前遍历到的字符串 $words[i]$ ，我们先算出对应的二进制数 $mask[i]$ ，然后再遍历 $j \in [0, i)$ 的所有字符串 $words[j]$ ，检查 $mask[i] \& mask[j] = 0$ 是否成立，如果成立就更新答案为 $\max(ans, |words[i]| \times |words[j]|)$ 。

遍历结束后，返回答案即可。

时间复杂度 $O(n^2 + L)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是字符串数组 $words$ 的长度，而 $L$ 是字符串数组所有字符串的长度之和。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        mask = [0] * len(words)
        ans = 0
        for i, s in enumerate(words):
            for c in s:
                mask[i] |= 1 << (ord(c) - ord("a"))
            for j, t in enumerate(words[:i]):
                if (mask[i] & mask[j]) == 0:
                    ans = max(ans, len(s) * len(t))
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate demonstrates understanding of bitwise operations and how they can optimize comparisons.
question_mark
Candidate is able to recognize the problem pattern of bit manipulation combined with array processing.
question_mark
Candidate provides an efficient solution that handles up to the input constraints.

warning

常见陷阱

外企场景

error
Not using bitwise operations correctly, leading to inefficient comparisons or incorrect results.
error
Failing to precompute the bitmask for each word, resulting in unnecessary recomputation during the pair comparison phase.
error
Overlooking edge cases, such as when no valid pairs of words exist, which would require returning 0.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Increasing the size of the input array and the length of each word to test the solution's scalability.
arrow_right_alt
Modifying the problem to consider uppercase letters or non-alphabetical characters and adjusting the bitmask approach accordingly.
arrow_right_alt
Introducing additional constraints such as limiting the number of words that can share common letters.

help

常见问题

外企场景

继续练习

#691 贴纸拼词 #943 最短超级串 #1177 构建回文串检测