用 int 做字符串 signature

Maximum Product of Word Lengths

这题本身不难，就是循环枚举。

关键点是“已知字母为 a-z，如何高效检查两个String是否有重复字符”

简单粗暴的方法就是 int[26] 的字母 hash，两个字符串之间用 26 次比较操作检查一下。

但是考虑到只有 26 种可能的时候，我们可以直接用 32-bit int 的 bit 来表示同样的信息，而且 int 之间可以直接通过 OR 和 AND 的位运算操作，大大减少每次比较所需要的时间。

注意点1：重复字符不要重复设，所以无脑加到 sig 上是不行的，要用 'OR'

public class Solution {
    public int maxProduct(String[] words) {
        if(words == null || words.length == 0) return 0;

        int[] signatures = new int[words.length];

        for(int i = 0; i < words.length; i++){
            String word = words[i];
            int sig = 0;
            for(int j = 0; j < word.length(); j++){
                int offset = word.charAt(j) - 'a';
                sig |= (1 << offset);
            }
            signatures[i] = sig;
        }

        int max = 0;

        for(int i = 0; i < words.length; i++){
            for(int j = i - 1; j >= 0; j--){
                if((signatures[i] & signatures[j]) == 0){
                    max = Math.max(max, words[i].length() * words[j].length());
                }
            }
        }

        return max;
    }
}