318. Maximum Product of Word Lengths

Problem

Tags: Array, String, Bit Manipulation

Given a string array words, return the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. If no such two words exist, return 0.

Example 1:

Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".

Example 2:

Input: words = ["a","ab","abc","d","cd","bcd","abcd"]
Output: 4
Explanation: The two words can be "ab", "cd".

Example 3:

Input: words = ["a","aa","aaa","aaaa"]
Output: 0
Explanation: No such pair of words.

Constraints:

• 2 <= words.length <= 1000
• 1 <= words[i].length <= 1000
• words[i] consists only of lowercase English letters.

Code

GO

// 318. Maximum Product of Word Lengths (4/5/53373)
// Runtime: 12 ms (73.08%) Memory: 6.45 MB (51.92%) 

func maxProduct(words []string) int {
	size := len(words)
	base := 'a'

	bitmap := [1001]int{0}
	for i, word := range words {
		for _, char := range word {
			pos := char - base
			bitmap[i] |= 1 << pos
		}
	}

	max := 0
	for i := 0; i < size; i++ {
		for j := i + 1; j < size; j++ {
			if (bitmap[i]&bitmap[j]) == 0 && len(words[i])*len(words[j]) > max {
				max = len(words[i]) * len(words[j])
			}
		}
	}

	return max
}

JS

// 318. Maximum Product of Word Lengths (2/19/53373)
// Runtime: 132 ms (82.35%) Memory: 46.50 MB (54.12%) 

/**
 * @param {string[]} words
 * @return {number}
 */

// 定義 bitmap 物件
// length 為原始字串長度, value 為 bitmap 值
class bm {
    constructor(string) {
        this.length = string.length;
        this.set(string);
    }

    set(string) {
        let v = 0;
        Array.from(new Set(string.split(""))).forEach((char) => {
            v += Math.pow(2, char.charCodeAt(0) - 97);
        });
        this.value = v;
    }
}

const maxProduct = function (words) {
    // 暫存最大值
    let max = 0;
    // 把 words 從 string 轉成上面定義的 bm
    words = words.map((word) => new bm(word));

    // 一一配對
    for (let i = 0; i < words.length; i++) {
        for (let j = i + 1; j < words.length; j++) {
            // 如果兩個 bm 做 bitwise AND 每項皆為 0 ，代表無碰撞，即為合法組，試圖更新暫存最大值
            if (!(words[i].value & words[j].value)) max = words[i].length * words[j].length > max ? words[i].length * words[j].length : max;
        }
    }
    return max;
};