专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
最近关于数字马力毁意向这件事在牛客网频频出现，原因就是数字马力发出的offer接受率高于预期，导致剩余缺口不多。那些OC过的可能收不到offer了，OC是什么意思呢？Offer Call简称OC，当面试官决定录用求职者后，HR会通过电话联系的方式询问求职者是否接受Offer，口头的形式，不是正式的书面offer。
虽然不是书面offer，但你之前Offer Call的时候给别人说打算录用你了，准备给你发offer了，而现在突然又不发了，这就叫毁意向。我们知道如果发了书面offer在返回是违法的，但这种口头承诺的offer，后面又不发了，到底违不违法？不管违不违法，反正是不得人心的。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第318题：最大单词长度乘积。
问题描述
来源：LeetCode第318题
难度：中等
给你一个字符串数组 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"。
2 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] 仅包含小写字母
问题分析
这题是让找出两个单词长度的最大乘积，并且这两个单词不能有公共的字母。计算单词长度的乘积比较简单，这里的关键点是怎么判断两个字符串是否有公共的字母。
因为提示中说了字符串仅包含小写字母，小写字母总共有26个，所以我们可以使用位运算来判断。对于每一个字符串都可以使用一个int类型的数字来标记，从右往左第一位是 a，第二位是 b ……，出现了哪个字母就在相应的位置标记为 1 。
如果两个数字通过与运算（&）结果为 0 ，说明这两个字符串没有公共的字母，可以计算它两长度的乘积，最后只需要保留最大乘积即可。
JAVA：
public int maxProduct(String[] words) { int length = words.length; // 记录每个字符串中有哪些字母 int[] bits = new int[length]; int ans = 0; for (int i = 0; i < length; i++) { // 标记当前字符串有哪些字母 for (char ch : words[i].toCharArray()) bits[i] |= 1 << (ch - 'a'); // 如果当前字符串和之前的字符串没有公共的字母，就计算他们的 // 乘积，保留最大值即可。 for (int j = 0; j < i; j++) { // 如果结果为0，表示他们没有公共的字母 if ((bits[i] & bits[j]) == 0) ans = Math.max(ans, (words[i].length() * words[j].length())); } } return ans; }C++：
public: int maxProduct(vector
&words) { int length = words.size(); // 记录每个字符串中有哪些字母 vector
bits(length); int ans = 0; for (int i = 0; i < length; i++) { // 标记当前字符串有哪些字母 for (char &ch: words[i]) bits[i] |= 1 << (ch - 'a'); // 如果当前字符串和之前的字符串没有公共的字母，就计算他们的 // 乘积，保留最大值即可。 for (int j = 0; j < i; j++) { // 如果结果为0，表示他们没有公共的字母 if ((bits[i] & bits[j]) == 0) ans = max(ans, int(words[i].size() * words[j].size())); } } return ans; }
Python：
def maxProduct(self, words: List[str]) -> int: length = len(words) # 记录每个字符串中有哪些字母 bits = [0] * length ans = 0 for i in range(0, length): # 标记当前字符串有哪些字母 for ch in words[i]: bits[i] |= 1 << (ord(ch) - ord('a')) # 如果当前字符串和之前的字符串没有公共的字母，就计算他们的 # 乘积，保留最大值即可。 for j in range(0, i): # 如果结果为0，表示他们没有公共的字母 if (bits[i] & bits[j]) == 0: ans = max(ans, len(words[i]) * len(words[j])) return ans笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。