未分類

Maximum Product of Word Lengths

BitManipulation, Go, LeetCode

Maximum Product of Word Lengths

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:

1
2
3
Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return 16
The two words can be "abcw", "xtfn".

Example 2:

1
2
3
Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return 4
The two words can be "ab", "cd".

Example 3:

1
2
3
Given ["a", "aa", "aaa", "aaaa"]
Return 0
No such pair of words.
提示 解題應用
BitManipulation 左移運算子

Default:

1
2
3
func maxProduct(words []string) int {
}

解答思路:

這題最主要是需要能夠快速的比較兩個字串的字母組合是否出現重覆，然而不管是用hashmap或者是陣列等方式將字母分別做儲存，都免不然要逐一比較而導致超時，但如果使用二進位的方式來儲存字母的話不但可以大幅減少使用的空間，兩個字串在判斷是否出現字母重覆更只要O(1)的時間複雜度，其做法是利用int所擁有的32位元分別代表32個位置，而a~z只會用上26個位置正好足以使用，如果該字母存在就在對應的位元位置上註記1(利用<<左移運算子將1移至目標位置)，如果要判斷兩字串是否出現字母重覆就只要將對應的兩個int做&AND，結果為0的話表示兩字串的字母皆未重覆，最後就是字串間不斷兩兩比較判斷找出相乘的最大長度為止。

程式碼解說:

一開始便初始化一個與字串陣列相同長度的數字陣列，其為利用二進位的方式來儲存字母的位置，因此接著便利用巢狀迴圈遍歷每個字串及字母，每次取出字母便減去97(ASCII值轉為1~26的值)，而該值便決定1要向左位移多少次才能移至位元的目標位置上(字母的對應位置)，接著再與先前的值做|OR以保留之前的字母位置

1
2
3
4
5
6
7
var max int
binWords := make([]int, len(words))
for i, word := range words {
	for _, char := range word {
		binWords[i] |= 1 << uint(char-97)
	}
}

有了所有字串的字母位置二進位紀錄後，最後就是字串間不斷兩兩比較判斷，如果取出同一個字串或是兩個二進位紀錄做&AND結果不為0(表示兩字串的字母出現重覆)，又或者字串長度相乘不比最大值大則通通跳過，直到出現完全符合條件的結果才將相乘的值放入最大值之中，最後待全數組合遍歷完畢才向上回傳最大值

1
2
3
4
5
6
7
8
9
for i, word1 := range binWords {
	for j, word2 := range binWords {
		if i == j || word1&word2 != 0 || len(words[i])*len(words[j]) <= max {
			continue
		}
		max = len(words[i]) * len(words[j])
	}
}
return max

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func maxProduct(words []string) int {
	var max int
	binWords := make([]int, len(words))
	for i, word := range words {
		for _, char := range word {
			binWords[i] |= 1 << uint(char-97)
		}
	}
	for i, word1 := range binWords {
		for j, word2 := range binWords {
			if i == j || word1&word2 != 0 || len(words[i])*len(words[j]) <= max {
				continue
			}
			max = len(words[i]) * len(words[j])
		}
	}
	return max
}

總結:

給一字串陣列要找出兩個字串不包含彼此之間的字母，且兩字串長度相乘要為最大值，最主要是需要能夠快速的比較兩個字串的字母組合是否出現重覆，其做法是利用int所擁有的32位元分別代表32個位置，而a~z只會用上26個位置正好足以使用，如果該字母存在就在對應的位元位置上註記1(利用<<左移運算子將1移至目標位置)，如果要判斷兩字串是否出現字母重覆就只要將對應的兩個int做&AND，結果為0的話表示兩字串的字母皆未重覆，最後就是字串間不斷兩兩比較判斷找出相乘的最大長度為止。

分享到