leetcode筆記之Maximum Product of Word Lengths

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:
Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return 16
The two words can be "abcw", "xtfn".

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

Example 3:
Given ["a", "aa", "aaa", "aaaa"]
Return 0
No such pair of words.

二. 題目分析

題目大意：給定一個字符串數組words，尋找length(words[i]) * length(words[j])的最大值，其中words[i] 和 words[j] 兩個單詞不包含相同的字母。你可以假設每一個單詞只包含小寫字母。如果不存在這樣的兩個單詞，結果返回0。

對於題目的要求，首先需要統計words中每個單詞的小寫字母a-z是否存在，然後一次枚舉words[i]和words[j]，找出最大長度maxLength。

這裡可以使用32位整數來表示每個單詞的字母存在情況。我們知道小寫字母a~z有26位，因此一個32位整數的低26位可以用於標記a~z各個字母是否出現，比如最低位標記'a'是否出現；第二位標記'b'是否出現…以此類推，以下給出兩個例子：

對於abcd，可被標記為：0000 0000 0000 0000 0000 0000 0000 1111

對於acxy，可被標記為：0000 0001 1000 0000 0000 0000 0000 0101

因此，只需申請一個int srtToBit[26]的數組，通過簡單的位操作即可完成字符串標記。

標記完成後，開始兩兩比較數組，如"abcd"被標記為：0000 0000 0000 0000 0000 0000 0000 1111，"wxyz"被標記為：1111 0000 0000 0000 0000 0000 0000 0000，由於兩字符串不含相同的字母，因此兩個整數值相與（&），結果必然為0，這樣，就找出了這樣的字符串對。

三. 示例代碼

class Solution {
public:
    int maxProduct(vector& words) {
        int SIZE = words.size();
        vector strToBit(SIZE);
        // 將各字符串轉換為32位整數，用各位上的狀態
        // 0 & 1 來表示是否出現對應的字母，如acxyz為
        // 1010 0000 0000 0000 0000 0000 0000 0111
        // 32為整數存放在數組strToBit中
        for (int i = 0; i < SIZE; ++i)
        {
            int temp = 0;
            for (int j = 0; j < words[i].size(); ++j)
            {
                temp |= (1 << ('x' - words[i][j]));

            }
            strToBit[i] = temp;
        }
        int maxLength = 0;
        // 分別對各字符串進行與運算
        for (int i = 0; i < SIZE - 1; ++i)
            for (int j = i + 1; j < SIZE; ++j)
                if ((strToBit[i] & strToBit[j]) == 0)
                    maxLength = max(maxLength, static_cast(words[i].size() * words[j].size()));

        return maxLength;
    }
};