Maximum Product of Word Lengths

發表於   |   分類於

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:

1
2
Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return 16

The two words can be “abcw”, “xtfn”.

Example 2:

1
2
Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return 4

The two words can be “ab”, “cd”.

Example 3:

1
2
Given ["a", "aa", "aaa", "aaaa"]
Return 0

No such pair of words.

使用一个int值来表示字符串中字符的出项情况。

注意使用 与操作（|=） 来生成int值。

当两个int值的 和操作（&）结果不为 0 时，说明它们的二进制表示至少有一个相同的位为 1 。这也就代表着对应的字符串中有相同的字符。

想了半天没有好方法，结果还是暴力求解最大值……

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:

    int ToInt(string& s)
    {
        int ans = 0;
        for (int i = 0; i < s.length(); ++i)
        {
            int n = s[i] - 'a';
            int k = 1 << n;
            ans |= k;
        }
        return ans;
    }

    int maxProduct(vector<string>& words) {

        vector<int> bitMap(words.size(),0);

        // build bitmap
        for (int i = 0; i < words.size(); ++i)
        {
            bitMap[i] = ToInt(words[i]);
        }

        int R = 0;

        for (int i = 0; i < words.size(); ++i)
        {

            for (int j = i; j < words.size(); ++j)
            {
                if (bitMap[i] & bitMap[j]) continue;
                int r = words[j].length() * words[i].length();
                if (r > R) R = r;
            }
        }

        return R;
    }
};