This is the 16th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

318. Maximum word length product

Given a string array of words, find the maximum length(word[I]) * length(word[j]) that contains no common letters. You can think of each word as containing only lowercase letters. If no such two words exist, return 0.

 

Example 1: input: [" abcw ", "baz", "foo", "bar", "XTFN", "abcdef"] output: 16 explanation: the two words "abcw", "XTFN". Example 2: input: [" a ", "ab", "ABC", "d", "CD" and "BCD", "abcd"] output: 4: this two word for "ab", the "CD". Example 3: input: [" a ", "aa", "aaa", "aaaa"] output: 0 explanation: there is no such two words.Copy the code

Tip:

  • 2 <= words.length <= 1000
  • 1 <= words[i].length <= 1000
  • Words [I] contains only lowercase letters

Their thinking

  1. Using bitwise operations, we use an int representation for each word, because each word contains only lowercase letters and only 26 letters exist, so we can use the lower 26 bits of the binary representation of int to indicate whether each letter ever appeared
  2. Using map de-weighting, if two words have exactly the same letter composition, we only need to record the larger word length, because when two words with exactly the same letter composition are paired with other words without a common letter, we only focus on the maximum length(word[I]) * length(word[j]).
  3. For int types converted from words, map is used to map the length of the original word.

code

class Solution {
public:
    int maxProduct(vector<string> &words) {


        map<int.int> mark;
        for (int i = 0; i < words.size(a); ++i) {int cur(0);
            for (auto c:words[i])
                cur |= (1 << (c - 'a'));
            if (mark.count(cur))
                mark[cur] = max((int)words[i].size(),mark[cur]);
            else mark[cur] = words[i].size(a); }int res(0);
        for (auto item:mark){
            for (auto item2:mark)
            {
                if (item2==item) continue;
                if (item.first+item2.first==(item2.first|item.first))
                    res=max(res,item2.second*item.second); }}returnres; }};Copy the code
  • Time complexity: O(L+n2)O(L +n ^2)O(L+n2), where L is the sum of all the word lengths in the array words\textit{words}words, and n is the length of the array words\textit{words}words.
  • Space complexity: O(n)O(n)O(n), where n is the length of the array words \textit{words}words. You need to create a hash table to record the maximum word length for each bitmask. The number of records in the hash table cannot exceed N.