318. Maximum Product of Word Lengths

Question

Given a string array words, return the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. If no such two words exist, return 0.

Solution

正常的思路可能是用哈希表保存字符串中出现过的字符。此时表的大小是26也是一个常数。

我们可以采用位运算进行状态压缩，通过一个整数的二进制位保存二十六个字符的存在状态。

状态压缩

我们采用一个整数数组bin[]储存状态压缩后的整数。

遍历每个字符串，在字符串中遍历每一个字符。
初始化整数bit为0。在遍历字符时计算当前字符与字符’a’距离的差n，然后将1左移n位，填入（或运算）整数bit中。

比较

遍历words[]中的两个字符串，当bin[i]与bin[j]进行与运算结果为0时，则两个字符串没有共同字符。
此时更新二者长度乘积的最大值max。

最后返回max即可。

时间复杂度：O(L + n2)。L为所有字符的总长度。

Code

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