leetcode 318. Maximum Product of Word Lengths 字符串长度乘积最大解 + 位向量来确定交集

喜欢ヅ旅行 2022-06-07 01:08 182阅读 0赞

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.

这道题最直接的方法就是循环遍历判断交集，然后做计算，要是直接使用HashSet肯定超时。所以暂时就想不到别的方法了，我在网上看到了一个使用位向量的方法，很不错。

**具体的做法直接看代码，我这里想说一下为什么可以这么做。按照题意，这里只涉及小写字母，那么小写字符做多26个，一个int至少32bit，所以这里可以使用一个为向量来表示一个字符串的集合，这就是这道题这么做的原因。**

不过这道题还有一个地方需要注意：**位操作运算的优先级，要注意添加括号**

代码如下：

import java.util.Arrays;
    /*
     * 这个问题的解决方法很一般，就是不断尝试所有的可能的len之乘积，
     * 然后得到最大值，问题的关键是如何快速的判断两个string的交集
     * 这里使用的是一个位变量来表示元素的重复
     * */
    class Solution 
    {
        public int maxProduct(String[] words) 
        {
            if(words==null || words.length<=0)
                return 0;
    
            int []mask=new int[words.length];
            Arrays.fill(mask, 0);
            for(int i=0;i<words.length;i++)
                for(int j=0;j<words[i].length();j++)
                    mask[i] = mask[i] | (1<<(int)(words[i].charAt(j)-'a'));
    
            int maxRes=0;
            for(int i=0;i<words.length;i++)
            {
                for(int j=i+1;j<words.length;j++)
                {
                    if((mask[i]&mask[j])==0)
                        maxRes=Math.max(maxRes, words[i].length() * words[j].length());
                }
            }
            return maxRes;
        }
    }

下面是C++的做法，这里使用了位向量来做交集的处理，很棒的想法，

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    
    using namespace std;
    
    
    class Solution 
    {
    public:
        int maxProduct(vector<string>& words) 
        {
            vector<int> mask(words.size(),0);
            for (int i=0;i<words.size();i++)
            {
                for (char a : words[i])
                {
                    mask[i] = mask[i] | (1 << ((int)(a - 'a')));
                }
            }
    
            int maxRes = 0;
            for (int i = 0; i < mask.size(); i++)
            {
                for (int j = i + 1; j < mask.size(); j++)
                {
                    if ((mask[i] & mask[j]) == 0)
                    {
                        int tmp = words[i].length()*words[j].length();
                        maxRes = max(maxRes,tmp);
                    }
                }
            }
            return maxRes;
        }
    };