[LeetCode] 318. Maximum Product of Word Lengths

轉自LeetCode

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.

Solution

這題加速的關鍵是要怎麼辨別兩個 word 有沒有用到共同字元

兩兩檢查一定不會過，等同於暴力解法

首先想到的是那是不是建一個 identifier，像是 #a#b 來區別

但這個可以來區別是不是同一個 word，但是字母順序打亂了

和題目要的不太一樣

參考了一些解法，想法沒錯，但要換個方式來找，這題要用mask的概念

26個字母都各自代表1個bit，所以可以用一個 int 來表示 mask

只要兩個 word 的 mask 互相取 and 後的值是 0，就代表沒有用到共同的字元

可以用 map 來存值，mask 當做 key，word.length 當作 value

那這邊還要注意的是 a 和 aaa 的 mask 是一樣的，因為只有第一個 bit 會是 1

但是長度是不一樣的，所以每次都要更新 map[mask] 的值

kotlin(參考解法)

	class Solution {
	fun maxProduct(words: Array<String>): Int {
	val map = mutableMapOf<Int,Int>()
	var ans = 0
	for(w in words) {
	var mask = 0
	for(c in w) {
	mask = mask or (1 shl (c-'a'))
	}
	map[mask] = Math.max(map[mask] ?: 0, w.length)
	for(m in map) {
	if((m.key and mask) == 0) {
	ans = Math.max(ans, m.value * w.length)
	}
	}
	}
	return ans
	}
	}

view raw maximum_poroduct_of_word_lengths.kt hosted with ❤ by GitHub