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
Used 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 & 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;
}
}
}