LeetCode 318. 最大单词长度乘积

约 4 分钟
文章信息 8 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 华为 快手 滴滴
标签
数组 字符串 位运算

题目描述

✅ 318. 最大单词长度乘积

image-20260928223511396

题意分析

选择两个没有任何公共字母的单词，返回它们长度乘积的最大值；不存在合法单词对时返回 0。单词本身允许重复字母，计算长度时也包含这些重复位置。

判断两个单词是否兼容，只需要知道各自出现过哪些字母，不关心字母顺序和出现次数。题目只有 26 种小写字母，可以把这个出现集合压缩到一个整数中。

解法：位掩码枚举单词对

核心思路

[!blue]

用整数的第 0 到第 25 位分别表示字母 a 到 z。扫描单词中的字符 c，用 1 << (c - 'a') 得到对应位，再通过按位或把它设为 1。同一字母出现多次仍只设置同一个位，不会影响其他字母。

两个掩码按位与时，只有双方都为 1 的位置才会保留下来。因此 (mask[i] & mask[j]) == 0 等价于没有公共字母，可以在常数时间判断一对单词是否合法。

预处理好每个单词的掩码和原始长度后，枚举所有 i < j 的单词对。合法时用两个原始长度相乘更新最大值，确保既不遗漏任何候选，也不把同一对重复处理。答案初始为 0，无合法配对时自然返回零。

解题步骤

  1. 为每个单词建立掩码，逐字符按位或置位，并记录该单词的完整长度。
  2. 枚举第一个单词下标 i，再枚举从 i + 1 开始的第二个下标 j。
  3. 若两个掩码按位与为零，计算 lengths[i] * lengths[j]，更新答案。
  4. 返回所有合法单词对中的最大长度乘积。

代码实现

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(S+n^2)$，S 为总字符数，预处理后每对常数判断。
  • 空间复杂度：$O(n)$，掩码与长度数组。

关键点总结

[!green]

  • 位掩码保存的是字母出现集合，按位与直接判断集合是否相交。
  • 预处理只扫描每个字符一次，之后每次配对都不需要重新遍历单词。
  • 掩码负责判断合法性，原始词长负责计算收益，两者不能互相替代。

易错点总结

[!yellow]

  • 置位使用按位或，不能用加法，否则重复字母可能产生进位，错误改变其他字母位。
  • 掩码中 1 的数量是不同字母数，不是单词长度，不能拿它计算乘积。
  • 判断条件是按位与为零，不是两个掩码不相等；不同字母集合仍可能含有公共字母。
  • 只枚举两个不同下标，并在没有合法单词对时保留答案 0。

相似题目

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