江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第318题：最大单词长度乘积

给你一个字符串数组 words ，找出并返回 length(words[i]) length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。

📖 文章摘要

本文详细解析LeetCode第318题“最大单词长度乘积”，这是一道位运算和字符串处理的问题。文章提供了基于位掩码的解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升位运算能力的程序员。

核心知识点： 位运算、字符串处理、哈希表
难度等级： 中等
推荐人群： 具有基础算法知识，想要提升位运算能力的程序员

题目描述

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

解题思路

方法：位运算

这道题可以使用位运算来高效判断两个单词是否有公共字母。

关键点：

  • 使用一个整数的26个位来表示单词中出现的字母
  • 两个数按位与为0表示没有公共字母
  • 预处理每个单词的位掩码，避免重复计算

具体步骤：

  1. 遍历每个单词，计算其位掩码
  2. 遍历所有单词对，检查是否有公共字母
  3. 如果没有公共字母，计算长度乘积并更新最大值

时间复杂度：O(n^2 + L)，其中n是单词数量，L是所有单词长度之和 空间复杂度：O(n)

图解思路

位掩码计算示例表

单词 包含字母 二进制表示 十进制值
“ab” a,b 000…011 3
“cd” c,d 000…1100 12
“abc” a,b,c 000…0111 7
“def” d,e,f 000…111000 56

单词对比较分析表

单词1 单词2 掩码1 掩码2 按位与结果 是否可用
“ab” “cd” 3 12 0 是
“ab” “ac” 3 5 1 否
“def” “abc” 56 7 0 是

代码实现

C# 实现

public class Solution {
    public int MaxProduct(string[] words) {
        int n = words.Length;
        int[] masks = new int[n];
        
        // 计算每个单词的位掩码
        for (int i = 0; i < n; i++) {
            foreach (char c in words[i]) {
                masks[i] |= 1 << (c - 'a');
            }
        }
        
        // 找出最大乘积
        int maxProduct = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((masks[i] & masks[j]) == 0) {
                    maxProduct = Math.Max(maxProduct, 
                                        words[i].Length * words[j].Length);
                }
            }
        }
        
        return maxProduct;
    }
}

Python 实现

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        # 使用字典存储位掩码，可以处理重复单词
        masks = {}
        
        # 计算每个单词的位掩码
        for word in words:
            mask = 0
            for c in word:
                mask |= 1 << (ord(c) - ord('a'))
            # 如果有重复单词，保留最长的
            masks[mask] = max(masks.get(mask, 0), len(word))
        
        # 找出最大乘积
        max_product = 0
        masks_items = list(masks.items())
        n = len(masks_items)
        
        for i in range(n):
            for j in range(i + 1, n):
                if masks_items[i][0] & masks_items[j][0] == 0:
                    max_product = max(max_product,
                                    masks_items[i][1] * masks_items[j][1])
        
        return max_product

C++ 实现

class Solution {
public:
    int maxProduct(vector<string>& words) {
        int n = words.size();
        vector<int> masks(n, 0);
        
        // 计算每个单词的位掩码
        for (int i = 0; i < n; i++) {
            for (char c : words[i]) {
                masks[i] |= 1 << (c - 'a');
            }
        }
        
        // 找出最大乘积
        int maxProduct = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((masks[i] & masks[j]) == 0) {
                    maxProduct = max(maxProduct, 
                                   (int)words[i].length() * (int)words[j].length());
                }
            }
        }
        
        return maxProduct;
    }
};

执行结果

C# 实现

  • 执行用时：84 ms
  • 内存消耗：39.8 MB

Python 实现

  • 执行用时：168 ms
  • 内存消耗：16.2 MB

C++ 实现

  • 执行用时：36 ms
  • 内存消耗：15.8 MB

性能对比

语言 执行用时 内存消耗 特点
C# 84 ms 39.8 MB 实现简洁，性能适中
Python 168 ms 16.2 MB 使用字典优化重复单词
C++ 36 ms 15.8 MB 性能最优，内存占用最小

代码亮点

  1. 🎯 使用位运算高效判断字母重复
  2. 💡 Python实现中使用字典处理重复单词
  3. 🔍 预处理位掩码避免重复计算
  4. 🎨 代码结构清晰，变量命名直观

常见错误分析

  1. 🚫 忘记处理重复单词的情况
  2. 🚫 位运算操作符优先级使用错误
  3. 🚫 整数溢出问题处理不当
  4. 🚫 没有考虑空字符串的情况

解法对比

解法 时间复杂度 空间复杂度 优点 缺点
位运算 O(n^2 + L) O(n) 判断重复字母效率高 需要理解位运算
集合比较 O(n^2 * k) O(n * k) 思路直观 性能较差

相关题目

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新至第318题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

  • 👍 点个赞，让更多人看到这篇文章
  • 📁 收藏文章，方便后续查阅复习
  • 🔔 关注作者，获取更多高质量算法题解
  • 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！