【Leetcode】Maximum Product of Word Lengths
2828 ワード
タイトルリンク:https://leetcode.com/problems/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.
考え方:1つのintを2進数にするのは32ビットで、そのうちの26ビットを利用して1つの単語にあるアルファベットが現れたかどうかを表し、2つの単語に共通アルファベットが含まれているかどうかを比較するときに両者のint数字を合わせることができ、結果が0であれば共通アルファベットがある.
アルゴリズム:
タイトル: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.
考え方:1つのintを2進数にするのは32ビットで、そのうちの26ビットを利用して1つの単語にあるアルファベットが現れたかどうかを表し、2つの単語に共通アルファベットが含まれているかどうかを比較するときに両者のint数字を合わせることができ、結果が0であれば共通アルファベットがある.
アルゴリズム:
public int maxProduct(String[] words) {
int max = 0;
int words_value[] = new int[words.length];
for (int i = 0; i < words.length; i++) {
for (int j = 0; j < words[i].length(); j++) {
char c = words[i].charAt(j);
words_value[i] = words_value[i] | (1 << (c - 'a'));// 1
}
}
for (int i = 0; i < words.length; i++) {
for (int j = i + 1; j < words.length; j++) {
int product = 0;
if ((words_value[i] & words_value[j]) == 0) {
product = words[i].length() * words[j].length();
}
max = Math.max(max, product);
}
}
return max;
}