[Leetcode学习-c++&java]Maximum Product of Word Lengths

问题:

难度:medium

说明:

给出一个字符串数组,然后将数组内两个没有字母重叠的字符串长度相乘,求最长的得数。

题目连接:https://leetcode.com/problems/maximum-product-of-word-lengths/

输入范围:

  • 2 <= words.length <= 1000
  • 1 <= words[i].length <= 1000
  • words[i] consists only of lowercase English letters.

输入案例:

Example 1:
Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".

Example 2:
Input: words = ["a","ab","abc","d","cd","bcd","abcd"]
Output: 4
Explanation: The two words can be "ab", "cd".

Example 3:
Input: words = ["a","aa","aaa","aaaa"]
Output: 0
Explanation: No such pair of words.

我的代码:

1、需要找出不含相同字母的字符串,可以考虑用hash,因为只有26个字母,所以考虑使用位标记来确定每一个字符串究竟有26个字母的哪些。

2、然后就进行暴力匹配,将两个字符串的 hash 进行并集,hash1 & hash2 == 0 来判断是否有重复的字母。

3、因为数组最多是固定长度1000个字符串,所以加个版本号和1000长数组就行了,这个和树形数组一样的概念

Java:

class Solution {
    private static int version = 0;
    private static int[] map = new int[1001], tag = new int[1001];
    public int maxProduct(String[] words) {
        int len = words.length, max = 0;
        for(int i = 0; i < len; i ++) {
            if(tag[i] != version) {
                map[i] = 0; tag[i] = version;
            }
            int hash = 0;
            for(char ch : words[i].toCharArray()) {
                int solt = 1 << (ch - 'a');
                hash |= solt;
            }
            map[i] = hash;
        }
        
        for(int i = 0; i < len; i ++) 
            for(int j = i + 1; j < len; j ++)
                if((map[i] & map[j]) == 0)
                    max = Math.max(max, words[i].length() * words[j].length());

        version ++;
        return max;
    }
}

C++:

static int cache[1001] = {0}, tag[1001] = {0}, version = 0;

class Solution {
public:
    int maxProduct(vector<string>& words) {
        for(int i = 0, size = words.size(); i < size; i ++) {
            string str = words[i];
            for(int j = 0, len = str.length(); j < len; j ++) {
                int solt = 1 << (str[j] - 'a');
                if(tag[i] != version) {
                    tag[i] = version;
                    cache[i] = 0;
                }
                cache[i] |= solt;
            }
        }
        int maxRes = 0;
        for(int i = 0, size = words.size(); i < size; i ++) 
            for(int j = i + 1; j < size; j ++) 
                if((cache[i] & cache[j]) == 0) maxRes = max(maxRes,(int)(words[i].length() * words[j].length()));
        version++;
        return maxRes;
    }
};

 

上一篇:1001 A+B Format (20分)


下一篇:1001系列之案例0002如何从斯德哥尔摩气温数据集中可视化挖掘