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

2022-08-22 22:02:28

最大單詞長度乘積

給你一個字串陣列 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
}