LeetCode 318. 最大单词长度乘积

Categories:

题目描述
思路分析
1. 解法一：位掩码（推荐）
相似题目

题目描述

✅ 318. 最大单词长度乘积

思路分析

解法一：位掩码（推荐）

核心思路：

将每个单词映射为 26 位掩码，表示出现过的字符。

两个单词无公共字母等价于掩码按位与为 0。

枚举单词对，更新最大长度乘积。

复杂度分析：

时间复杂度：O(n^2 + total)，其中 n 表示单词数量。

空间复杂度：O(n)，用于掩码数组。

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

        for (int i = 0; i < n; i++) {
            int bit = 0;
            for (char c : words[i].toCharArray()) {
                bit |= 1 << (c - 'a');
            }
            mask[i] = bit;
            len[i] = words[i].length();
        }

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

        return res;
    }
}

func maxProduct(words []string) int {
	n := len(words)
	mask := make([]int, n)
	lens := make([]int, n)

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

	res := 0
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			if mask[i]&mask[j] == 0 {
				prod := lens[i] * lens[j]
				if prod > res {
					res = prod
				}
			}
		}
	}

	return res
}

相似题目

题目	难度	考察点
1178. 猜字谜	困难	位掩码
212. 单词搜索 II	困难	Trie
720. 词典中最长的单词	简单	字符串
820. 单词的压缩编码	中等	字符串
1048. 最长字符串链	中等	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/49508122