Go Java算法最大單詞長度乘積示例詳解

更新時間：2022年08月22日 15:41:46 作者：黃丫丫

這篇文章主要為大家介紹了Go Java算法最大單詞長度乘積示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪

最大單詞長度乘積

給你一個字符串數(shù)組 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）

為了得到最大單詞長度乘積，樸素的做法是，遍歷字符串數(shù)組 words 中的每一對單詞，判斷這一對單詞是否有公共字母，如果沒有公共字母，則用這一對單詞的長度乘積更新最大單詞長度乘積。

題目約定了每個單詞僅包含小寫字母，所以，我們可以將單詞中的每個字母都映射到一個 int 類型的不同位上，這樣，就做到了每個單詞都對應一個 int 類型的數(shù)值，這樣的話，我們對比兩個單詞是否包含相同的字母，只需要把它們對應的 int 數(shù)值做 & 運算，看是不是等于 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：數(shù)組中所有單詞的長度之和

n：數(shù)組長度

時間復雜度：o（l+n^2）

空間復雜度：o（n）

方法一：位運算（go）

具體的方法思路已經(jīng)在上文中表述，詳情請看上文內(nèi)容

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：數(shù)組中所有單詞的長度之和

n：數(shù)組長度

時間復雜度：o（l+n^2）

空間復雜度：o（n）

以上就是Go Java算法最大單詞長度乘積示例詳解的詳細內(nèi)容，更多關于Go Java算法單詞長度乘積的資料請關注腳本之家其它相關文章！

您可能感興趣的文章: