LeetCode 318. 最大单词长度乘积

2025-06-12 HGNULB 约 10 分钟

文章信息 8 个分类 3 个标签

分类

题目描述

✅ 318. 最大单词长度乘积

题意分析

给一个字符串数组，从中挑出两个不共享任何字母的单词，让它们长度的乘积最大，返回这个最大值；如果任意两个单词都有公共字母，返回 0。

「不共享任何字母」是唯一的约束，它只关心两个单词各自出现过哪些字母，完全不关心每个字母出现了几次、出现在什么位置。这条信息一旦被识别出来，就等于说：一个单词在判重时的全部有效信息，可以被压缩成一个「字母是否出现」的集合。

约束里另外两个数字给出了明确信号：字符串只含小写英文字母，也就是最多 26 种；单词数量规模在千级别。26 这个数小于 32，意味着一个 int 就能装下整个字母集合；千级别的 $n$ 意味着 $O(n^2)$ 的两两枚举完全可以接受，不需要更花哨的做法。所以真正需要优化的不是「枚举多少对」，而是「判断一对要花多久」。

边界：数组只有一个单词时不存在任何一对，答案为 0；所有单词两两都有公共字母时答案同样是 0，所以答案初值取 0 而不是负无穷；单词长度乘积最大约为 1000 × 1000，int 不会溢出；题面不保证单词互不相同，重复的两个单词一定有公共字母（除非是空串，而题面保证长度至少为 1），会被自然排除。

解法：位掩码枚举单词对

核心思路

先看暴力做法：枚举所有下标对 (i, j)，对每一对再拿两层循环逐字符比较，看有没有相同字母。判断一对的代价是 $O(L_i \times L_j)$，总代价能到 $O(n^2 L^2)$。即使用 HashSet 优化成把一个单词装进集合再遍历另一个，单次判断也还是 $O(L)$。瓶颈很清楚：同一个单词在 $n$ 次配对里被反复重新扫描，做了大量重复劳动。

顺着这个瓶颈想：既然一个单词参与判断时唯一有用的信息是「它含有哪些字母」，那就把这份信息预处理一次、复用 $n$ 次。而「26 个字母各自在或不在」正是一个 26 位的布尔向量，用整数的二进制位来表示最省：第 $k$ 位为 1 表示字母 'a' + k 出现过。

于是得到本解法的核心不变量：mask[i] 的第 $k$ 位为 1，当且仅当字母 'a' + k 在 words[i] 中出现过；lengths[i] 恒等于 words[i].length()。在这个表示下，「两个单词共享某个字母」等价于「存在某一位在两个掩码上同时为 1」，也就是 mask[i] & mask[j] != 0。取反即得判定式：
\[\text{words}[i] \text{ 与 } \text{words}[j] \text{ 无公共字母} \iff \text{mask}[i] \mathrel{\&} \text{mask}[j] = 0\]
这一步把单次判断从 $O(L)$ 压到了 $O(1)$——一条按位与指令。整体复杂度随之从 $O(n^2 L)$ 降到 $O(n^2 + L_{\text{total}})$，其中预处理只扫一遍全部字符。

剩下的就是常规的最大值维护：对每一对通过判定的 (i, j)，用 lengths[i] * lengths[j] 更新答案。注意只枚举 j > i，因为乘积对称，枚举一半就够。

解题步骤

开两个长度为 n 的数组 mask 与 lengths。为什么要单独存长度：后面的双层循环里会访问 $O(n^2)$ 次长度，存成 int 数组比每次调用 words[i].length() 更直接，也让主循环里完全不再触碰字符串。

对每个单词扫一遍字符，执行 bitMask |= 1 << (c - 'a')。为什么用 |= 而不是 +=：同一个字母可能出现多次，|= 幂等，重复置位不改变结果；用加法会进位到相邻位，直接破坏「一位代表一个字母」的语义。

把算好的掩码与长度写回数组。为什么必须先全部预处理完再进入配对循环：预处理是 $O(L)$ 一次性开销，若放进配对循环内部就退化成每对重算，优化前功尽弃。

双层循环枚举 i 从 0 到 n-1、j 从 i+1 到 n-1。为什么 j 从 i+1 起：一是避免 i == j 自己和自己配对（自己和自己必然有公共字母，虽然会被判定式挡住，但语义上不该出现），二是 (i,j) 与 (j,i) 乘积相同，枚举上三角即可省掉一半。

判定 (mask[i] & mask[j]) == 0 才更新答案。为什么括号不能省：Java 与 Go 中 & 的优先级低于 ==，写成 mask[i] & mask[j] == 0 在 Java 里直接编译报错，在其他语言里可能被解析成 mask[i] & (mask[j] == 0)，语义完全错。

答案初值取 0 并原样返回。为什么不是 -1 或负无穷：题面规定不存在合法配对时就返回 0，初值 0 让这种情况自然落入主逻辑，无需任何特判。

以 具体用例 words = ["abcw","baz","foo","bar","xtfn","abcdef"] 走一遍。

预处理阶段，把每个单词转成掩码（这里用出现的字母集合来表示更直观）：abcw → {a,b,c,w}，长度 4；baz → {a,b,z}，长度 3；foo → {f,o}，长度 3；bar → {a,b,r}，长度 3；xtfn → {f,n,t,x}，长度 4；abcdef → {a,b,c,d,e,f}，长度 6。注意 foo 里的两个 o 只置位一次，这正是 |= 的幂等性在起作用。

配对阶段，answer 初值 0：
i=0(abcw) 与 j=1(baz)：都含 a、b，按位与非 0，跳过。与 j=2(foo)：{a,b,c,w} 与 {f,o} 无交集，按位与为 0，乘积 4 × 3 = 12，answer 更新为 12。与 j=3(bar)：共享 a、b，跳过。与 j=4(xtfn)：{a,b,c,w} 与 {f,n,t,x} 无交集，乘积 4 × 4 = 16，answer 更新为 16。与 j=5(abcdef)：共享 a，跳过。
i=1(baz)：与 foo 无交集，乘积 3 × 3 = 9，不超过 16；与 xtfn 无交集，乘积 3 × 4 = 12，不超过 16；与 bar、abcdef 都共享 a，跳过。
i=2(foo)：与 bar 无交集，乘积 3 × 3 = 9；与 xtfn 共享 f，跳过；与 abcdef 共享 f，跳过。
i=3(bar)：与 xtfn 无交集，乘积 3 × 4 = 12；与 abcdef 共享 a、b，跳过。
i=4(xtfn) 与 j=5(abcdef)：共享 f，跳过。
循环结束，返回 answer = 16，对应 abcw 与 xtfn。

代码实现

class Solution {
    // 两个单词没有公共字母，等价于它们的位掩码按位与结果为 0。
    public int maxProduct(String[] words) {
        int n = words.length;
        int[] mask = new int[n];
        int[] lengths = new int[n];

        for (int i = 0; i < n; i++) {
            int bitMask = 0;
            for (int j = 0; j < words[i].length(); j++) {
                bitMask |= 1 << (words[i].charAt(j) - 'a');
            }
            mask[i] = bitMask;
            lengths[i] = words[i].length();
        }

        int answer = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((mask[i] & mask[j]) == 0) {
                    answer = Math.max(answer, lengths[i] * lengths[j]);
                }
            }
        }

        return answer;
    }
}

func maxProduct(words []string) int {
    // 两个单词没有公共字母，等价于它们的位掩码按位与结果为 0。
    n := len(words)
    mask := make([]int, n)
    lengths := make([]int, n)

    for i, word := range words {
        bitMask := 0
        for j := 0; j < len(word); j++ {
            bitMask |= 1 << (word[j] - 'a')
        }
        mask[i] = bitMask
        lengths[i] = len(word)
    }

    answer := 0
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            if mask[i]&mask[j] == 0 {
                product := lengths[i] * lengths[j]
                if product > answer {
                    answer = product
                }
            }
        }
    }

    return answer
}

复杂度分析

时间复杂度：$O(n^2 + L)$，其中 $L$ 是所有单词的总字符数。凭什么：预处理阶段每个字符只被访问一次，合计 $O(L)$；配对阶段上三角共 $n(n-1)/2$ 对，每对只做一次按位与、一次比较、一次乘法，全是常数指令，合计 $O(n^2)$。关键在于字符串长度 $L$ 与配对次数 $n^2$ 从相乘变成了相加。

空间复杂度：$O(n)$。凭什么：只额外开了 mask 与 lengths 两个长度为 $n$ 的整型数组，每个单词的字母集合被压缩进单个 int，与单词本身的长度无关。

关键点总结

「只关心字母是否出现」是压缩成位掩码的触发条件。一旦发现题目对某个维度只需要「在/不在」的布尔判断，且取值种类不超过 64，就应立刻想到用整数的二进制位表示集合。

集合运算与位运算的对应关系要背熟：交集是 &，并集是 |，对称差是 ^，判空是 == 0，加入元素是 |= 1 << k，判断元素是否存在是 (mask >> k) & 1。本题只用到「交集为空」这一条。

把 $O(n^2)$ 内层的重复计算提到循环外预处理，是从 $O(n^2 L)$ 降到 $O(n^2 + L)$ 的通用手法，和「前缀和」「预处理哈希」属于同一类思想。

|= 的幂等性正是处理重复元素所需要的语义，用 += 或 ++ 计数会破坏位与位之间的独立性。

答案初值的选取应让「无解」自然成立。这里题面规定无解返回 0，恰好等于乘积的下界，所以初值 0 既是答案也是哨兵，一个特判都不用写。

面试视角：这道题的考点百分之百是「你能不能想到位掩码」，用 HashSet 求交集虽然也能过但直接绕开了考点。写完后主动补一句「掩码可以进一步用哈希表按掩码去重，只保留每个掩码下最长的单词，当重复单词很多时能显著减少配对数」，是很自然的加分延伸。

易错点总结

错误写法：if (mask[i] & mask[j] == 0)（漏掉外层括号） → 在 Java 中 == 优先级高于 &，表达式变成 mask[i] & (mask[j] == 0)，int 与 boolean 做按位与，编译直接报错；在优先级不同的语言里则会静默算出完全错误的结果。

错误写法：bitMask += 1 << (c - 'a') → 用例 words = ["aa","b"]，字母 a 被加两次，bitMask 从 1 变成 2，被误认成含有字母 b，于是 "aa" 与 "b" 被判为有公共字母，答案错成 0（正确答案是 2）。

错误写法：内层循环写成 for (int j = 0; j < n; j++) 且不跳过 i == j → 用例 words = ["abc"] 之外的任意输入下，mask[i] & mask[i] 只有在单词为空串时才为 0；题面虽保证长度至少为 1 使这条侥幸不出错，但一旦允许空串（如 words = [""]），就会拿同一个单词自乘，答案错成 0 与实际语义不符，且白跑一倍循环。

错误写法：answer 初值设成 Integer.MIN_VALUE → 用例 words = ["a","ab","abc"]，任意两词都共享字母 a，一次都不进入更新分支，最终返回 -2147483648 而不是题目要求的 0。

错误写法：预处理写在配对双层循环内部，每次现算两个单词的掩码 → 用例 words 含 1000 个长度 1000 的单词时，重复扫描字符导致约 $10^9$ 次字符操作，直接超时。

错误写法：1 << (c - 'a') 写成 1 << c → 用例 words = ["a","z"]，'a' 的 ASCII 是 97，1 << 97 在 Java 中按 97 % 32 = 1 处理得到 2，'z' 的 122 按 122 % 32 = 26 得到 1 << 26，两个掩码碰巧不冲突结果对了，但换成 ["a","b"] 时 'a' → 1<<1、'b' → 1<<2 也不冲突，而 ["a","!"] 这类越界字符会让位彻底错乱；根本问题是没有把字符归一化到 0~25。

错误写法：用 HashSet<Character> 存字母并调用 retainAll 判交集 → 用例 1000 个长单词时虽然逻辑正确，但每次判交集是 $O(26)$ 的对象操作外加大量装箱，实测比按位与慢一到两个数量级；面试中这么写等于放弃了本题唯一的考点。

错误写法：只用掩码不存长度，判定通过后回头写 words[i].length() * words[j].length() → 逻辑正确但把字符串对象的方法调用放进了 $O(n^2)$ 的热循环，在 Java 中还可能触发额外的边界检查；用例规模拉满时是明显的常数级劣化。

错误写法：认为掩码相同的单词一定可以互相替换而只保留第一个 → 用例 words = ["ab","abab"]，两者掩码相同但长度不同，若保留的是较短的 "ab"，与某个无冲突单词配对时会算出偏小的乘积；去重时必须保留同掩码下最长的那个。

相似题目

题目	难度	考察点
LCR 005. 最大单词长度乘积	中等	与本题同题，可直接套用同一份代码
1239. 串联字符串的最大长度	中等	从「两两配对」升级为「任意子集拼接」，需要回溯或子集 DP 来累积掩码
982. 按位与为零的三元组	困难	判定条件从两元变三元，靠预统计所有两两与值的频次把 $O(n^3)$ 降下来
1178. 猜字谜	困难	判定从「交集为空」变成「子集关系」，要枚举掩码的所有子集来做匹配统计
78. 子集	中等	直接用 0 到 $2^n-1$ 的整数枚举全部子集，是把整数当集合看的最基础练习
187. 重复的DNA序列	中等	每个碱基编成 2 位，用滑动窗口维护定长子串的整数编码，考的是位编码而非集合
421. 数组中两个数的最大异或值	中等	同样是两两配对求极值，但靠 01 字典树按位贪心把 $O(n^2)$ 优化到 $O(n)$
698. 划分为k个相等的子集	中等	用掩码表示「哪些元素已被选走」，是状态压缩 DP 的典型入口