Question

Formatted question description: https://leetcode.ca/all/318.html

 318	Maximum Product of Word Lengths

 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.

Algorithm

Use mask.

Because the title is all lowercase letters, so there are only 26 digits, and an integer int has 32 digits.

We can use the last 26 digits to correspond to 26 letters. If it is 1, it means that the letter in the corresponding position has appeared.

Then each word can be represented by an int number.

The condition that two words have no common letter is that the two int numbers ‘&’ op are 0

Code

Java

public class Maximum_Product_of_Word_Lengths {

    public class Solution {
        public int maxProduct(String[] words) {
            if (words == null || words.length <= 1) {
                return 0;
            }

            int n = words.length;
            int[] encodedWords = new int[n];

            // setup encoding map
            for (int i = 0; i < words.length; i++) {
                String word = words[i];
                for (int j = 0; j < word.length(); j++) {
                    char c = word.charAt(j);
                    encodedWords[i] |= (1 << (c - 'a')); // set to 1 for bit c-'a'
                }
            }

            int maxLen = 0;
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    if ((encodedWords[i] & encodedWords[j]) == 0) {
                        maxLen = Math.max(maxLen, words[i].length() * words[j].length());
                    }
                }
            }

            return maxLen;
        }
    }
}

// OJ: https://leetcode.com/problems/maximum-product-of-word-lengths/
// Time: O(N^2)
// Space: O(N)
class Solution {
public:
    int maxProduct(vector<string>& A) {
        int N = A.size();
        if (N == 0) return 0;
        vector<int> bit(N);
        for (int i = 0; i < N; ++i) {
            for (char c : A[i]) {
                bit[i] |= (1 << (c - 'a'));
            }
        }
        int ans = 0;
        for (int i = 0; i < N; ++i) {
            for (int j = i + 1; j < N; ++j) {
                if ((bit[i] & bit[j]) == 0) {
                    ans = max(ans, (int)(A[i].size() * A[j].size()));
                }
            }
        }
        return ans;
    }
};

class Solution(object):
  def maxProduct(self, words):
    """
    :type words: List[str]
    :rtype: int
    """
    bitmap = [0] * len(words)
    mask = 0x01
    ans = 0
    for i in range(0, len(words)):
      word = words[i]
      for c in word:
        bitmap[i] |= (mask << (ord(c) - ord('a')))
    for i in range(0, len(words)):
      for j in range(0, i):
        if bitmap[i] & bitmap[j] == 0:
          ans = max(ans, len(words[i]) * len(words[j]))

    return ans

318 - Maximum Product of Word Lengths

Question

Algorithm

Code

All Problems

All Solutions