Go Java算法最大單詞長度乘積示例詳解
最大單詞長度乘積
給你一個字符串數組 words ，找出並返回 length(words[i]) * length(words[j]) 的最大值，並且這兩個單詞不含有公共字母。如果不存在這樣的兩個單詞，返回 0 。
*示例 1：
輸入：words = ["abcw","baz","foo","bar","xtfn","abcdef"]
輸出：16
解釋：這兩個單詞為 "abcw", "xtfn"。
- 示例 2：
輸入：words = ["a","ab","abc","d","cd","bcd","abcd"]
輸出：4
解釋：這兩個單詞為 "ab", "cd"。
- 示例 3：
輸入：words = ["a","aa","aaa","aaaa"]
輸出：0
解釋：不存在這樣的兩個單詞。
方法一：位運算（java）
為瞭得到最大單詞長度乘積，樸素的做法是，遍歷字符串數組 words 中的每一對單詞，判斷這一對單詞是否有公共字母，如果沒有公共字母，則用這一對單詞的長度乘積更新最大單詞長度乘積。
題目約定瞭每個單詞僅包含小寫字母，所以，我們可以將單詞中的每個字母都映射到一個 int 類型的不同位上，這樣，就做到瞭每個單詞都對應一個 int 類型的數值，這樣的話，我們對比兩個單詞是否包含相同的字母，隻需要把它們對應的 int 數值做 & 運算，看是不是等於 0 即可，如果等於 0 ，說明沒有相同的位是 1，也就不存在相同的字母。
這樣，我們在比較兩個單詞是否沒有公共字母的時候隻要直接按位與一下即可，沒有公共字母應該得到的值是0，其他情況得到的值都不為零。
class Solution {
public int maxProduct(String[] words) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
int length = words.length;
for (int i = 0; i < length; i++) {
int mask = 0;
String word = words[i];
int wordLength = word.length();
for (int j = 0; j < wordLength; j++) {
mask |= 1 << (word.charAt(j) - 'a');
}
if (wordLength > map.getOrDefault(mask, 0)) {
map.put(mask, wordLength);
}
}
int maxProd = 0;
Set<Integer> maskSet = map.keySet();
for (int mask1 : maskSet) {
int wordLength1 = map.get(mask1);
for (int mask2 : maskSet) {
if ((mask1 & mask2) == 0) {
int wordLength2 = map.get(mask2);
maxProd = Math.max(maxProd, wordLength1 * wordLength2);
}
}
}
return maxProd;
}
}
l：數組中所有單詞的長度之和
n：數組長度
時間復雜度：o（l+n^2）
空間復雜度：o（n）
方法一：位運算（go）
具體的方法思路已經在上文中表述，詳情請看上文內容
func maxProduct(words []string) int {
hash := func(word string) int {
res := 0
for _, r := range word{
res |= 1 << (r - 'a')
}
return res
}
m, ans := map[int]int{}, 0
for _, word := range words {
h := hash(word)
if m[h] < len(word) {
for other, v := range m {
if((other & h) == 0){
if tmp := v * len(word); tmp > ans {
ans = tmp
}
}
}
m[h] = len(word)
}
}
return ans
}
l：數組中所有單詞的長度之和
n：數組長度
時間復雜度：o（l+n^2）
空間復雜度：o（n）
以上就是Go Java算法最大單詞長度乘積示例詳解的詳細內容，更多關於Go Java算法單詞長度乘積的資料請關註WalkonNet其它相關文章！