[Leetcode] Maximum Product of Word Lengths, Solution

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.

[Thoughts]
这里面比较有意思的是，只需要判断两个words是否有重复字符，并不需要知道具体重复的次数，所以用bitmap来做，很方便。

一个integer是32个bit，而英文字母只有26个，所以在第一轮循环中，先处理word，把26个字母是否出现映射到bitmap上。在第二轮循环中，对于bitmap不重复的words，计算长度的乘积，并保留最大值。


[Code]

1:    int maxProduct(vector<string>& words) {  
2:        
3:      if(words.size() < 2) return 0;  
4:      vector<int> counts(words.size(), 0);  
5:        
6:      for(int k = 0; k< words.size(); k++) {  
7:        string word = words[k];  
8:        int measure = 0;  
9:        for(int i =0; i< word.size(); i++)  
10:        {  
11:          // set bitmap  
12:          measure |= (1<< (word[i]-'a'));  
13:        }  
14:        counts[k] = measure;  
15:      }  
16:        
17:      int max_v = 0;  
18:      for(int i =0; i< words.size(); i++) {  
19:        for(int j = i+1; j< words.size(); j++)  
20:        {  
21:          // use bitmap to check no common char  
22:          if((counts[i] & counts[j]) ==0) {  
23:            int product= words[i].length()* words[j].length();  
24:            max_v = max(max_v, product);  
25:          }  
26:        }  
27:      }  
28:      return max_v;   
29:    }