LeetCode LCR 005. 最大单词长度乘积

约 5 分钟
文章信息 5 个分类 4 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
数组 字符串 LCR 位运算

题目描述

✅ LCR 005. 最大单词长度乘积

image-20260928234642470

image-20260928234642472

题意分析

从字符串数组中选择两个不同下标的单词，要求两者没有任何公共字母，返回它们原始长度乘积的最大值。若没有合法配对，返回零。

所有单词非空且只含小写英文字母。判断能否配对只关心出现过哪些字母，但计算乘积仍要使用完整单词长度，重复字母也占长度，不能把两个含义混为一谈。

解法：字母集合位掩码

核心思路

[!blue]

每个单词会参与多次配对，若每次重新扫描字符判断交集，就会反复构造同一份集合。先把每个单词的字母集合预处理好，再在不同单词间复用。

字符集只有二十六个小写字母，因此一个整数的低二十六位足以记录出现情况。令 mask[i] 的第 c - 'a' 位为一，表示该单词出现过字符 c，建表时使用按位或 mask[i] |= 1 << (c - 'a')。

按位或重复设置同一位不会改变结果，正好对应“出现过即可”；如果改用加法，重复字符会产生进位，破坏其他字母的位置。掩码有意忽略出现次数和顺序，这不会影响两个单词是否有公共字母。

两个掩码按位与后，某位为一恰好表示对应字母在两边都出现。因此 (mask[i] & mask[j]) == 0 当且仅当两个单词无公共字母；通过判定后，用两个原长度的乘积更新最大值。

每对只需检查一次，内层从 j = i + 1 开始，既排除自己与自己配对，也避免反向重复枚举。答案从零开始，没有任何合法配对时自然保持零。

解题步骤

  1. 创建与单词数等长的掩码数组，初始全部为零。
  2. 每个单词只扫描一次，将出现字母对应的位用按位或设为一。
  3. 枚举所有 i < j 的单词对，按位与为零才计算原单词长度乘积。
  4. 持续保存最大乘积并返回。

代码实现

class Solution {
    public int maxProduct(String[] words) {
        int n = words.length;
        int[] mask = new int[n];

        // 预处理：每个单词的字母集合压进一个 int 的低 26 位，只算一次。
        for (int i = 0; i < n; ++i) {
            for (char c : words[i].toCharArray()) {
                mask[i] |= 1 << (c - 'a');
            }
        }

        int answer = 0;

        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                // 按位与为 0 等价于两个字母集合不相交。
                if ((mask[i] & mask[j]) == 0) {
                    answer = Math.max(answer, words[i].length() * words[j].length());
                }
            }
        }

        return answer;
    }
}

func maxProduct(words []string) (answer int) {
    n := len(words)
    mask := make([]int, n)
    // 预处理：每个单词的字母集合压进一个整数的低 26 位，只算一次。
    for i, w := range words {
        for _, c := range w {
            mask[i] |= 1 << (c - 'a')
        }
    }
    for i, x := range mask {
        for j := i + 1; j < n; j++ {
            // 按位与为 0 等价于两个字母集合不相交。
            if x&mask[j] == 0 {
                answer = max(answer, len(words[i])*len(words[j]))
            }
        }
    }
    return
}

复杂度分析

设 n 为单词数，S 为全部单词字符总数，Lmax 为最长单词长度。

  • 时间复杂度：$O(S + n^2)$，预处理每个字符一次，配对阶段每对仅做常数次位运算和长度计算。
  • 空间复杂度：掩码表占 $O(n)$。Java 代码在处理单词时调用 toCharArray()，峰值还需要 $O(Lmax)$ 的临时字符数组，因此额外空间为 $O(n + Lmax)$；Go 的当前实现为 $O(n)$。

关键点总结

[!green]

  • 掩码表示字母是否出现，原单词长度表示总字符数，两者分别用于合法性和得分。
  • 有限的二十六字母集合可以放入整数的低二十六位，按位与直接表示集合交集。
  • 预处理将单词集合从重复计算变为一次构造、多次使用。
  • 置位使用按位或，重复字符不会改变集合。

易错点总结

[!yellow]

  • 用加法累积字母标记，重复字母会使位产生进位。
  • Java 中应写完整括号 (mask[i] & mask[j]) == 0，避免位与和比较的优先级混淆。
  • 乘积使用原单词长度，不能用掩码里一的数量代替。
  • 两个单词只要有一个公共字母就不合法，不需要整个掩码相同。
  • 这份单整数掩码依赖小写英文字母范围，不能不改表示就套到任意字符集。

相似题目

题目 难度 关联与区别
1178. 猜字谜 困难 同样用字母位掩码表示出现集合，原题按谜面子集匹配，本题用按位与为0判断不相交。
1239. 串联字符串的最大长度 中等 同样要求字符集合不重叠，原题可选多个串，需要在选择过程中合并掩码。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/20011689
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！