BiruLyu
5/24/2017 - 5:04 PM

318. Maximum Product of Word Lengths.java

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

["abcw","baz","foo","bar","xtfn","abcdef"]
["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
["a", "aa", "aaa", "aaaa"]

*/