leetcode-max-product-of-word-lengths

题目大意

　　https://leetcode.com/problems/maximum-product-of-word-lengths/

　　字符串数组，找出其中满足两个字符串没有公共字符的长度之积的最大值，注意字符仅是26个英文字母

题目分析

　　既然只含有26个英文字母，我们可以预先扫描一下字符串数组，计算每个字符串有那些字符，然后hash到一个int，最终生成flag数组。然后O(n^2)扫描任意两个字符串，看他们flag的并运算的值，如果为0，那么就不含有公共字符，思路还是比较容易。

代码

public class Solution {
    public int maxProduct(String[] words) {
        if (words == null || words.length == 0) {
            return 0;
        }
        int len = words.length;
        //预处理生成flag数组
        int[] flag = new int[len]; //保存每个字符串含有那些字符
        int[] l = new int[len]; //保存每个字符串的长度
        for (int i = 0; i < len; i++) {
            char[] array = words[i].toCharArray();
            int len2 = array.length;
            l[i] = len2;
            for (int j = 0; j < len2; j++) {
                flag[i] |= (1 << (array[j] - 'a'));
            }
        }
        // o(n^2)遍历任意两个字符串
        int max = 0;
        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                if ((flag[i] & flag[j]) == 0) {
                    max = Math.max(max, l[i] * l[j]);
                }
            }
        }
        return max;
    }
}