剑指 Offer II 005. 单词长度的最大乘积

给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。

示例 1:

输入: words = [“abcw”,“baz”,“foo”,“bar”,“fxyz”,“abcdef”]
输出: 16
解释: 这两个单词为 “abcw”, “fxyz”。它们不包含相同字符，且长度的乘积最大。
示例 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] 仅包含小写字母

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/aseY1I
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析

方法一：哈希表
用哈希表记录字符串中出现的字符。
对于每个字符串，用哈希表记录出现在该字符串中的所有字符，定义一个words.length * 26的二维Boolean类型的数组，行代表每个字符串，遍历字符串数组每个字符串的每个字符，如果字符串中有某个字符就在对应的位置上赋值true，全部赋值完成后，再次遍历字符串，将当前字符串与后面所有字符串进行比较，如果没有重复的字符就记录两者长度的乘积，最后返回最大的乘积。
方法二：二进制
用整数的二进制数位记录字符串中出现的字符。方法一是用长度26的Boolean数组记录字符串中出现的字符，考虑到Boolean类型只有true和false，可以记录为0和1，Java中int型整数的二进制形式有32位，只需要26位就可以记录字符串中出现的字符，因此可以用一个int型整数来记录字符，如果字符串中有字符’a’，那么最右边整数为1，如果有字符’b’，那么倒数第2位为1，依次类推，对两个字符串进行判断时进行与运算，如果为0说明没有重复字符。

题解（Java）

方法一：哈希表

class Solution {public int maxProduct(String[] words) {boolean[][] flags = new boolean[words.length][26];for (int i = 0; i < words.length; i++) {for (char c : words[i].toCharArray()) {flags[i][c - 'a'] = true;}}int ans = 0;for (int i = 0; i < words.length; i++) {for (int j = i + 1; j < words.length; j++) {int k = 0;for (; k < 26; k++) {if (flags[i][k] && flags[j][k]) break; }if (k == 26) {int num = words[i].length() * words[j].length();ans = Math.max(ans, num);}}}return ans;}
}

方法二：二进制

class Solution {public int maxProduct(String[] words) {int ans = 0, len = words.length;int[] nums = new int[len];for(int i = 0; i < len; i++){for(int j = 0, size = words[i].length(); j < size; j++){nums[i] |= 1 << (words[i].charAt(j) - 'a');}}for(int i = 0; i < len; i++){for(int j = i + 1; j < len; j++){if((nums[i] & nums[j]) == 0) ans = Math.max(ans, words[i].length() * words[j].length());}}return ans;}
}