快捷導(dǎo)航

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

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

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

最大單詞長度乘積

給你一個(gè)字符串?dāng)?shù)組 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且這兩個(gè)單詞不含有公共字母。如果不存在這樣的兩個(gè)單詞，返回 0 。

*示例 1：

輸入：words = ["abcw","baz","foo","bar","xtfn","abcdef"]

輸出：16

解釋：這兩個(gè)單詞為 "abcw", "xtfn"。

示例 2：

輸入：words = ["a","ab","abc","d","cd","bcd","abcd"]

輸出：4

解釋：這兩個(gè)單詞為 "ab", "cd"。

示例 3：

輸入：words = ["a","aa","aaa","aaaa"]

輸出：0

解釋：不存在這樣的兩個(gè)單詞。

方法一：位運(yùn)算（java）

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

題目約定了每個(gè)單詞僅包含小寫字母，所以，我們可以將單詞中的每個(gè)字母都映射到一個(gè) int 類型的不同位上，這樣，就做到了每個(gè)單詞都對(duì)應(yīng)一個(gè) int 類型的數(shù)值，這樣的話，我們對(duì)比兩個(gè)單詞是否包含相同的字母，只需要把它們對(duì)應(yīng)的 int 數(shù)值做 & 運(yùn)算，看是不是等于 0 即可，如果等于 0 ，說明沒有相同的位是 1，也就不存在相同的字母。

這樣，我們?cè)诒容^兩個(gè)單詞是否沒有公共字母的時(shí)候只要直接按位與一下即可，沒有公共字母應(yīng)該得到的值是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ù)組長度

時(shí)間復(fù)雜度：o（l+n^2）

空間復(fù)雜度：o（n）

方法一：位運(yùn)算（go）

具體的方法思路已經(jīng)在上文中表述，詳情請(qǐ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ù)組長度

時(shí)間復(fù)雜度：o（l+n^2）

空間復(fù)雜度：o（n）

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

您可能感興趣的文章: