2023-11-06 LeetCode每日一题（最大单词长度乘积）

2023-11-06每日一题

一、题目编号

318. 最大单词长度乘积

二、题目链接

点击跳转到题目位置

三、题目描述

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

示例 1：

示例 2：

示例 3：

提示：

• 2 <= words.length <= 1000
• 1 <= words[i].length <= 1000
• words[i] 仅包含小写字母

四、解题代码

class Solution {
public:int maxProduct(vector<string>& words) {int n = words.size();vector<int> mask(n);for(int i = 0; i < n; ++i){string word = words[i];for(int j = 0; j < word.size(); ++j){mask[i] |= 1 << (word[j] - 'a');}}int max_length = 0;for(int i = 0; i < n; ++i){for(int j = i + 1; j < n; ++j){if(((mask[i] & mask[j]) == 0)){max_length = max(max_length, (int)words[i].size() * (int)words[j].size());}}}return max_length;}
};

五、解题思路

(1) 使用位运算中的或运算得到每个字符串的二进制编码。

(2) 两个二进制编码进行按位与运算得到是否有相同字符。

(3) 满足条件后更新最大的单词长度成绩。