我用了O（n2） brute force解法，以為會超時，結(jié)果還好。擊敗了11%的人。然后看了下答案，很多人用了位運算判斷有沒有相似字母，但是時間復雜度跟我一樣呀。?？赡苁莃it manipulation就是比較快吧。

    public int maxProduct(String[] words) {
        if (words == null || words.length <= 1)
            return 0;
        int max = 0;
        for (int i = 0; i < words.length - 1; i++) {
            for (int j = i + 1; j < words.length; j++) {
                if (!haveCommonLetter(words[i], words[j])) {
                    max = Math.max(words[i].length() * words[j].length(), max);
                }
            }
        }
        return max;
    }

    private boolean haveCommonLetter(String s1, String s2) {
        int[] map = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            map[s1.charAt(i) - 'a']++;
        }
        for (int i = 0; i < s2.length(); i++) {
            if (map[s2.charAt(i) - 'a'] != 0) {
                return true;
            }
        }
        return false;
    }

bit manipulation的方法：

    public int maxProduct(String[] words) {
        if (words == null || words.length == 0)
            return 0;
        int len = words.length;
        int[] value = new int[len];
        for (int i = 0; i < len; i++) {
            String tmp = words[i];
            value[i] = 0;
            for (int j = 0; j < tmp.length(); j++) {
                value[i] |= 1 << (tmp.charAt(j) - 'a');
            }
        }
        int maxProduct = 0;
        for (int i = 0; i < len; i++)
            for (int j = i + 1; j < len; j++) {
                if ((value[i] & value[j]) == 0 && (words[i].length() * words[j].length() > maxProduct))
                    maxProduct = words[i].length() * words[j].length();
            }
        return maxProduct;
    }

我理解了半天，確實因為bit manipulation不常用很難一眼看出來。它用了這樣一句：

                value[i] |= 1 << (tmp.charAt(j) - 'a');

其實就是，int有32位，字母有26個，正好還多6個，可以用了mapping；于是它就把1向左移動，a移動0位，z移動25位，這樣的話比如dba就成了1011,用int表示是19。|= 這種計算很像安卓里面用來判斷兩個屬性是不是同時存在，比如xml布局里那種。最后判斷兩個數(shù)是否有重疊字母就相與一下。挺fancy的，我遇到這種題一般喜歡用array模擬map，這里提供了另一種思路。

另外，還注意到另一個人寫了一個帶有prunning字樣的代碼，就是先判斷兩個字符串長度，再判斷是不是hasCommon，可以減少幾次循環(huán)，不過string.length()代碼我感覺也是要for循環(huán)的吧。。。看了String的源碼，沒找到實現(xiàn)。

public class Solution {
    public int maxProduct(String[] words) {
        int max = 0;

        Arrays.sort(words, new Comparator<String>(){
            public int compare(String a, String b){
                return b.length() - a.length();
            }
        });

        int[] masks = new int[words.length]; // alphabet masks

        for(int i = 0; i < masks.length; i++){
            for(char c: words[i].toCharArray()){
                masks[i] |= 1 << (c - 'a');
            }
        }
    
        for(int i = 0; i < masks.length; i++){
            if(words[i].length() * words[i].length() <= max) break; //prunning
            for(int j = i + 1; j < masks.length; j++){
                if((masks[i] & masks[j]) == 0){
                    max = Math.max(max, words[i].length() * words[j].length());
                    break; //prunning
                }
            }
        }

        return max;
    }
}

扯的有點遠了。

ref：
https://discuss.leetcode.com/topic/35539/java-easy-version-to-understand/2