单词长度的最大乘积

给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。

1.暴力法

暴力法虽然测试用例能正确输出，但是程序时间复杂度太高直接超时，

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
class Solution {
public:
    bool have_same_char(string str1, string str2) {
        for (char c = 'a'; c <= 'z'; ++c) {
            int flag1 = 0;
            int flag2 = 0;
            for (int i = 0; i < str1.size(); ++i) if (str1[i] == c) {flag1 = 1; break;}
            for (int i = 0; i < str2.size(); ++i) if (str2[i] == c) {flag2 = 1; break;}
            if (flag1 && flag2) return true;
        }
        return false;
    }

    int maxProduct(vector<string>& words) {
        int max = 0;
        for (int i = 0; i < words.size(); ++i) {
            for (int j = i; j < words.size(); ++j) {
                int temp = words[i].size() * words[j].size();
                if (!have_same_char(words[i], words[j]) && temp > max) {
                    max = temp;
                }
            }
        }
        return max;
    }
};

2.位运算

核心思想：

  1. 使用一个 int 来代指某个 word[i]：低 26 来代指字母 a-z 是否出现过，
  2. 然后对每个字符对对应的两个 int 值执行 & 操作（若两字符无重复字符，则结果为 0），并得出最终答案。

image-20230424001843547

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
class Solution {
public:
    int max(int a, int b) { return a > b ? a : b; }
    int maxProduct(vector<string>& words) {
        int len = words.size();
        int *masks = new int[len];
        int idx = 0;
        //1.对vector<string>数组进行预处理 对words中的每个string 中的每个char进行位运算 使其便于处理
        for (string word : words) {
            int temp = 0;
            for (int i = 0; i < word.size(); ++i) temp |= (1 << word[i] - 'a');
            masks[idx++] = temp;
        }

        //2.对二进制数进行暴力遍历操作
        int ans = 0;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if ((masks[i] & masks[j]) == 0)
                    ans = max(ans, words[i].length() * words[j].length());//不重复
            }
        }
        return ans;
    }
};

3.位运算优化

参考：https://leetcode.cn/problems/aseY1I/solutions/1746734/by-ac_oier-qk3a/

对于词频相同（mask值相等）的两字符，只需要保留字符长度大的即可，因此可以使用哈希表代替 masks 数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int max(int a, int b) { return a > b ? a : b; }
    int maxProduct(vector<string>& words) {
        unordered_map<int, int> unmap;
        //1.对vector<string>数组进行预处理 对words中的每个string 中的每个char进行位运算 使其便于处理
        for (string word : words) {
            int temp = 0;
            int len = word.size();
            for (int i = 0; i < word.size(); ++i) temp |= (1 << (word[i] - 'a'));
            if (!unmap.count(temp) || (unmap[temp] < len)) unmap.insert(make_pair(temp, len));
        }

        //2.对二进制数进行暴力遍历操作
        int ans = 0;
        for (auto a : unmap) {
            for (auto b : unmap) {
                if ((a.first & b.first) == 0) ans = max(ans, a.second * b.second);
            }
        }
        return ans;
    }
};