ETH官方钱包

前往
大廳
主題

LeetCode - 318. Maximum Product of Word Lengths 解題心得

Not In My Back Yard | 2021-07-05 00:00:03 | 巴幣 0 | 人氣 515

題目連結:


題目意譯:
給一定一個字串陣列 words ,回傳 length(word[i]) × length(word[j]) 的最大值,其中兩個字詞沒有任何相同的字母。如果沒有這樣子的兩個字詞存在,回傳 0 。

限制:
2 ≦ words.length ≦ 1000
1 ≦ words[i].length ≦ 1000
words[i] 只由小寫英文字母組成。



範例測資:
範例 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
解釋: 沒有這種字詞對。


解題思維:
因為字串們只由小寫英文字母組成,而英文字母只有 26 個。因此我們可以利用一個 32 位元整數來儲存一個字串有的字母之情形。例如 00……01011 代表著有一個字串有著字母 A 、 B 和 D (每個數字從低位到高位分別對應著 A 到 Z)。

接著我們預先掃過每個字串並利用上面的技巧統計出每個字串的字母出現情形,並將這些數字存在於一個陣列 M 之中以便存取。

接著我們用雙層迴圈窮舉出所有的 (i, j) 數對。每個 (i, j) 數對對應著一個字串對 (words[i], words[j]) 。

接著我們利用剛剛預先求出的陣列 M 判斷目前窮舉出的字串對是否有著相同的字母。而這個判斷可以用以下方式得出:
M[i] & M[j] == 0
其中「&」代表著 AND 之位元運算。因為當兩個字串有著相同字母時,同一位置的位元在兩個字串將都會是 1 ,因此會使得 AND 操作後的數字結果不為 0 。

所以當 AND 結果為 0 時,便表示著兩個字串沒有相同的字母。此時我們可以將兩個字串的長度相乘,得到一個乘積。而這些乘積之中最大的即是所求。如果沒有任何乘積出現,則回傳 0 。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作