leetcode_318 最大单词乘积

1. 题意

给定一个字符串数组，找出不含重复字母的两个字符串长度乘积最大值。
最大单词乘积

2. 题解

位运算压缩

2.1 位运算压缩

class Solution {
public:
    int maxProduct(vector<string>& words) {

        vector<pair<int,int>> chCnt;

        for (string &word: words) {
            int ans = 0;

            for (char c:word) {
                ans |= 1 <<(c -'a');
            }
            chCnt.push_back({ans, static_cast<int>(word.size())});
        }

        int sz = words.size();

        int ans = 0;
        for (int i = 0; i < sz - 1; ++i) {
            for (int j = i + 1;j < sz; ++j) {
                if (chCnt[i].first & chCnt[j].first)
                    continue;
                ans = max(chCnt[i].second * chCnt[j].second, ans);
            }
        }

        return ans;
    }
};
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

2.2 一个小优化

对于含有相同种类字母的，选最长的那个。

class Solution {
public:
    int maxProduct(vector<string>& words) {

        // vector> chCnt;
        unordered_map<int, int> chCnt;
        for (string &word: words) {
            int ans = 0;

            for (char c:word) {
                ans |= 1 <<(c -'a');
            }

            if ( chCnt.count(ans)) {
                if (static_cast<int>(word.size()) >　chCnt[ans]) {
                    chCnt[ans] = static_cast<int>(word.size());
                }
            }
            else {
                chCnt[ans] = static_cast<int>(word.size());
            }
        }

        int sz = words.size();
        int ans = 0;

        for (auto &[k1,v1]:chCnt) {
            for (auto &[k2,v2]:chCnt) {
                if ( !(k1 & k2)) {
                    ans = max(ans, v1 * v2);
                }
            }
        }

        return ans;
    }
};
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