Cinte's Leetcode Record
0%

318. 最大单词长度乘积

Posted on Edited on In Disqus:
Symbols count in article: 987 Reading time ≈ 1 mins.

318. 最大单词长度乘积

位运算来判断是否有重复数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int maxProduct(vector<string>& words) {
        int n = words.size();
        vector<int> memo;
        memo.reserve(n);
        size_t ret = 0;
        for(auto& str : words)
        {
            int tmp = 0;
            for(auto ch : str)
                tmp |= 1 << (ch - 'a');
            memo.push_back(tmp);
        }
        for(int i = 0; i < n; ++i)
            for(int j = 1 + 1; j < n; ++j)
                if((memo[i] & memo[j]) == 0)
                    ret = max(ret, words[i].size() * words[j].size());
        return ret;
    }
};

O(n^2 + 所有字符串长度)

优化空间，记录有相同字母的字符串的最大长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int maxProduct(vector<string>& words) {
        int n = words.size();
        unordered_map<int, int> memo;
        int ret = 0;
        for(auto& str : words)
        {
            int tmp = 0;
            for(auto ch : str)
                tmp |= 1 << (ch - 'a');
            memo[tmp] = max(memo[tmp], int(str.size()));
        }
        for(auto i = memo.begin(); i != memo.end(); ++i)
        {
            auto j = i;
            ++j;
            for(; j != memo.end(); ++j)
                if((i->first & j->first) == 0)
                    ret = max(ret, i->second * j->second);
        }
        return ret;
    }
};