318. Maximum Product of Word Lengths

https://leetcode.com/problems/maximum-product-of-word-lengths/

Python

Use Hashmap

• Time: O(N^2)
• Space: O(N)

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        mapper = [set(word) for word in words]

        ans = 0

        for i in range(len(words)):
            for j in range(i+1, len(words)):
                if not mapper[i] & mapper[j]:
                    ans = max(ans, len(words[i])*len(words[j]))
        return ans

Javascript

var maxProduct = function(words) {
  const intArray = words.map(word => toInt(word));
  let max = 0;

  for (let i = 0; i < intArray.length - 1; i++) {
    for (let j = i + 1; j < intArray.length; j++) {
      if ((intArray[i] & intArray[j]) === 0) {
        max = Math.max(max, words[i].length * words[j].length);
      }
    }
  }

  return max;
};

const toInt = (word) => {
  let num = 0;
  const base = ('a').charCodeAt(0);

  for (const char of word) {
    num |= 1 << char.charCodeAt(0) - base;
  }
  return num;
}