https://gist.github.com/gcrfelix/5ef95b029011304e3771
给你一个很大的字典。一对词如果不share 任何字母,比如dog, cat不share字母,则是interesting pair,
而dog, boy就share一个o,则不是interesting pair.
找出所以interesting pairs中长度乘积最大的pair.输出这个乘积。
解法:
N^2的复杂度。 每个单词都可以预处理成一个整数 (bit pattern)比如
0 0 0 1 1 1 代表所以出现abc的单词。
f e d c b a
然后单词1和单词2的bit pattern 取&,看结果是不是为0
public int getBitPattern(String word) {
int x = 0;
word = word.toLowerCase();
for(int i=0; i<word.length(); i++) {
char c = word.charAt(i);
x = x | (1 << (c - 'a'));
}
return x;
}
public boolean isInterestingPair(String word1, String word2) {
int bit1 = getBitPattern(word1);
int bit2 = getBitPattern(word2);
if(bit1 & bit2 == 0) {
return true;
}
return false;
}
给你一个很大的字典。一对词如果不share 任何字母,比如dog, cat不share字母,则是interesting pair,
而dog, boy就share一个o,则不是interesting pair.
找出所以interesting pairs中长度乘积最大的pair.输出这个乘积。
解法:
N^2的复杂度。 每个单词都可以预处理成一个整数 (bit pattern)比如
0 0 0 1 1 1 代表所以出现abc的单词。
f e d c b a
然后单词1和单词2的bit pattern 取&,看结果是不是为0
public int getBitPattern(String word) {
int x = 0;
word = word.toLowerCase();
for(int i=0; i<word.length(); i++) {
char c = word.charAt(i);
x = x | (1 << (c - 'a'));
}
return x;
}
public boolean isInterestingPair(String word1, String word2) {
int bit1 = getBitPattern(word1);
int bit2 = getBitPattern(word2);
if(bit1 & bit2 == 0) {
return true;
}
return false;
}