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.
public class Solution { public int maxPRoduct(String[] words) { if (words == null || words.length == 0) return 0; int[] values = new int[words.length]; for (int i = 0; i < words.length; i++){ String word = words[i]; for (int j = 0; j < word.length(); j++) { values[i] |= 1 << word.charAt(j) - 'a'; } } int res = 0; for (int i = 0; i < words.length; i++) { for (int j = i+1; j < words.length; j++) { if((values[i] & values[j]) == 0 && res < words[i].length() * words[j].length()) res = words[i].length() * words[j].length(); } } return res; }}新闻热点
疑难解答
