LeetCode 0318 - Maximum Product of Word Lengths

Reck Zhang

发布于 2021-08-11 11:57:14

2780

Maximum Product of Word Lengths

Desicription

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:

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

Example 2:

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

Example 3:

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

Solution

class Solution {
public:
    int maxProduct(std::vector<std::string>& words) {
        auto visits = std::vector<std::bitset<26>>(words.size(), 0);
        for(int i = 0; i < words.size(); i++) {
            auto word = words[i];
            for(char c : word) {
                visits[i][c - 'a'] = true;
            }
        }

        int maxLength = 0;
        for(int i = 0; i < words.size(); i++) {
            for(int j = i + 1; j < words.size(); j++) {
                if((visits[i] & visits[j]).to_ulong() == 0) {
                    maxLength = std::max(maxLength, (int)words[i].size() * (int)words[j].size());
                }
            }
        }

        return maxLength;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019-05-17，如有侵权请联系 cloudcommunity@tencent.com 删除

product