318. Maximum Product of Word Lengths

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:

Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return 16
The two words can be "abcw", "xtfn".

Example 2:

Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return 4
The two words can be "ab", "cd".

Example 3:

Given ["a", "aa", "aaa", "aaaa"]
Return 0
No such pair of words.

这个题是bit manipulation的题。一开始看的时候就觉得是O(n^2) 的题但是没有仔细想。因为string compare也是要花时间的。因此如果把string compare 转换成O(1)就会节约出来string compare的复杂度。因为题目要求是两个string没有共同的character，那么我们可以用两个数字表示它们各自的character情况（类似set），然后我们比较两个数字即可！

 public int maxProduct(String[] words) {  
     int n = words.length;  
     if(n == 0) return 0;  
     int[] values = new int[n];  
     for(int i =0; i < n; i++){  
       for(int j = 0; j < words[i].length(); j++){  
         int d = words[i].charAt(j) - 'a';  
         values[i] |= 1 << d;// trick  
       }  
     }  
     int max = 0;  
     for(int i = 0; i < n; i++){  
       for(int j = i+1; j < n; j++){  
         if((values[i] & values[j]) == 0 && max < words[i].length() *words[j].length()){  
           max = words[i].length() *words[j].length();  
         }  
       }  
     }  
     return max;  
   }