Description：
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
No such pair of words.
Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.
Subscribe to see which companies asked this question
題目大意：找出不包含相同字母的單詞長度乘積的最大值
思路：最容易想到的辦法應該是3層循環枚舉，找出最大值，複雜度是O(n^2*k)，k為單詞的長度。在此基礎上優化，優化判斷兩個單詞是否包含相同字母部分，可以使用26位的整數來表示單詞的字母情況，每個字母在這個整數的二進制數中都有一個位置，如果為1代表包含這個字母，否則相反。再通過兩個整數按位與來判斷是否包含相同字母，如果不包含相同字母則兩個整數的二進制數中必然沒有對應位置都為1的位，則按位與後得0。這樣優化之後複雜度變為O(n^2)。還可以再優化，可以預先把字元串數組按長度降序排序，這樣在尋找最大乘積的時候就可以盡早的找到，不做過多的計算。但是這種優化不是一定能提高效率的，因為如果遇到最後的結果是比較小的情況，并不能避免大量的計算，還增加了排序的開銷。
含有排序優化的實作代碼：
public class Solution {
public int maxProduct(String[] words) {
int[] map = new int[words.length];
//長度由大到小排序
Arrays.sort(words, new Comparator<String>() {
public int compare(String s1, String s2) {
return s2.length() - s1.length();
}
});
//用26位整數記錄包含字母的情況
for(int i=0; i<words.length; i++) {
int bit = 0;
for(int j=0; j<words[i].length(); j++) {
bit |= (1 << words[i].charAt(j) - 'a');
}
map[i] = bit;
}
int max = 0;
//找出滿足條件的最大乘積
for(int i=0; i<words.length; i++) {
if(words[i].length()*words[i].length() <= max) break; //往後沒有更大的了
for(int j=i+1; j<words.length; j++) {
if((map[i] & map[j]) == 0) { //沒有相同的字母
max = Math.max(max, words[i].length() * words[j].length()); //一次循環中最大的
break;
}
}
}
return max;
}
}