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.
class Solution { public int maxProduct(String[] words) { int l = words.length; int res = 0; if(l == 0) return res; // if(l == 1) return for(int i = 0; i < l - 1; i++){ for(int j = i + 1; j <l; j++){ String t1 = words[i]; String t2 = words[j]; boolean t = true; for(int m = 0; m < t1.length(); m++){ for(int n = 0; n < t2.length(); n++){ if(t1.charAt(m) == t2.charAt(n)){ t = false; break; } } if(t == false) break; } if(t == true) res = Math.max(res, t1.length() * t2.length()); } } return res; } }
brute force
public class Solution { public int maxProduct(String[] words) { final int n = words.length; final boolean[][] hashset = new boolean[n][26]; for (int i = 0; i < n; ++i) { for (int j = 0; j < words[i].length(); ++j) { hashset[i][words[i].charAt(j) - ‘a‘] = true; } } int result = 0; for (int i = 0; i < n-1; ++i) { for (int j = i + 1; j < n; ++j) { boolean hasCommon = false; for (int k = 0; k < 26; ++k) { if (hashset[i][k] && hashset[j][k]) { hasCommon = true; break; } } int tmp = words[i].length() * words[j].length(); if (!hasCommon && tmp > result) { result = tmp; } } } return result; } // private static final int ALPHABET_SIZE = 26; }
318. Maximum Product of Word Lengths
原文：https://www.cnblogs.com/wentiliangkaihua/p/11706504.html