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:

Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]

Return 16

The two words can be "abcw", "xtfn".

Example 2:

Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]

Return 4

The two words can be "ab", "cd".

Example 3:

Given ["a", "aa", "aaa", "aaaa"]

Return 0

No such pair of words.

分析

由于只有26个小写字母，所以，我们可以为数组中的每个word开辟一个长为26的布尔数组作为哈希表，然后用一个两重for循环，两两比较，如果不存在公共的字母，则计算二者的长度的乘积，取最大作为最终结果。时间复杂度O(26n^2)，空间复杂度O(26n)。

上面的方法可以进一步优化，即长度为26的布尔数组，小于32位，可以编码为一个整数，这样两个整数按位与，如果结果为1，说明存在公共字母，如果结果为0，说明不存在公共字母。时间复杂度O(n^2)，空间复杂度O(n)。

解法1

  1. // Maximum Product of Word Lengths
  2. // Time Complexity: O(26n^2), Space Complexity: O(26n)
  3. public class Solution {
  4.     public int maxProduct(String[] words) {
  5.         final int n = words.length;
  6.         final boolean[][] hashset = new boolean[n][ALPHABET_SIZE];
  8.         for (int i = 0; i < n; ++i) {
  9.             for (int j = 0; j < words[i].length(); ++j) {
  10.                 hashset[i][words[i].charAt(j) - 'a'] = true;
  11.             }
  12.         }
  14.         int result = 0;
  15.         for (int i = 0; i < n; ++i) {
  16.             for (int j = i + 1; j < n; ++j) {
  17.                 boolean hasCommon = false;
  18.                 for (int k = 0; k < ALPHABET_SIZE; ++k) {
  19.                     if (hashset[i][k] && hashset[j][k]) {
  20.                         hasCommon = true;
  21.                         break;
  22.                     }
  23.                 }
  24.                 int tmp = words[i].length() * words[j].length();
  25.                 if (!hasCommon && tmp > result) {
  26.                     result = tmp;
  27.                 }
  28.             }
  29.         }
  30.         return result;
  31.     }
  32.     private static final int ALPHABET_SIZE = 26;
  33. }

解法2

  1. // Maximum Product of Word Lengths
  2. // Time Complexity: O(n^2), Space Complexity: O(n)
  3. public class Solution {
  4.     public int maxProduct(String[] words) {
  5.         final int n = words.length;
  6.         final int[] hashset = new int[n];
  8.         for (int i = 0; i < n; ++i) {
  9.             for (int j = 0; j < words[i].length(); ++j) {
  10.                 hashset[i] |= 1 << (words[i].charAt(j) - 'a');
  11.             }
  12.         }
  14.         int result = 0;
  15.         for (int i = 0; i < n; ++i) {
  16.             for (int j = i + 1; j < n; ++j) {
  17.                 int tmp = words[i].length() * words[j].length();
  18.                 if ((hashset[i] & hashset[j]) == 0 && tmp > result) {
  19.                     result = tmp;
  20.                 }
  21.             }
  22.         }
  23.         return result;
  24.     }
  25. }

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/bitwise-operations/maximum-product-of-word-lengths.html