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.
最直接的想法，两两比较，算出最大值。
其中比较的操作要做n^2次，只能用效率高的位运算。
先遍历一遍words，把单词转成二进制的数。
a对应2的0次，b对应2的1次，以此类推。
| z | y | ... | d | c | b | a |
| 2^25 | 2^24 | ... | 4 | 2 | 1 | 0 |
比较两个单词是不是包含重复字母的时候，只需要用&运算看结果是否为0。
1 /** 2 * @param {string[]} words 3 * @return {number} 4 */ 5 var maxProduct = function(words) { 6 var i, j, max = 0; 7 var bitDict = []; 8 for(i = 0; i < words.length; i++) 9 bitDict[i] = word2Num(i); 10 for(i = 0; i < words.length; i++) 11 for(j = 0; j < words.length; j++) 12 if(i !== j && !hasSharedLetter(i, j)) 13 max = Math.max(max, words[i].length * words[j].length); 14 return max; 15 16 function word2Num(index){ 17 var res = 0, charCodeA = ‘a‘.charCodeAt(); 18 for(var i = 0 ; i < words[index].length; i++) 19 res |= Math.pow(2, words[index][i].charCodeAt() - charCodeA); 20 return res; 21 } 22 function hasSharedLetter(index1, index2){ 23 if((bitDict[index1] & bitDict[index2]) === 0) return false; 24 return true; 25 } 26 };
[LeetCode][JavaScript]Maximum Product of Word Lengths
原文：http://www.cnblogs.com/Liok3187/p/5061408.html