Monday, August 7, 2017

[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]

[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:    }
``````