LeetCode 題目解析：Maximum Product of Word Lengths (單詞長度最大乘積)

題目描述

給定一個字串陣列 words，找出 length(word[i]) * length(word[j]) 的最大值，其中兩個單詞 word[i] 和 word[j] 不包含相同的字母。假設每個單詞僅包含小寫字母。若不存在這樣的單詞對，返回 0。

範例 1

輸入：["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
輸出：16
說明：符合條件的單詞對為 "abcw" 和 "xtfn"，長度乘積為 4 × 4 = 16。

範例 2

輸入：["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
輸出：4
說明：符合條件的單詞對為 "ab" 和 "cd"，長度乘積為 2 × 2 = 4。

範例 3

輸入：["a", "aa", "aaa", "aaaa"]
輸出：0
說明：不存在無共同字母的單詞對。

解題思路

核心挑戰在於高效判斷兩個單詞是否包含相同字母。暴力法檢查每對單詞的字母集合會導致 O(n² × m) 的時間複雜度（n 為單詞數，m 為平均長度），對大規模輸入效率較低。

利用位運算可將每個單詞的字母集合壓縮為一個 32 位整數：

• 小寫字母 a-z 共 26 個，恰好可用 32 位整數的低 26 位表示。
• 第 i 位為 1 表示對應字母（'a' + i）出現在單詞中，為 0 表示未出現。
• 例如 "abcd" 對應二進位 0000...00001111（低 4 位為 1）；"acxy" 對應 0000...0110000000000101。

兩單詞無共同字母 ⇔ 它們的位掩碼 & 運算結果為 0。預先計算所有單詞的位掩碼後，雙重迴圈檢查所有單詞對，時間複雜度降為 O(n² + n × m)，空間複雜度 O(n)。

參考代碼 (C++)

class Solution {
public:
    int maxProduct(vector<string>& words) {
        int n = words.size();
        vector<int> mask(n, 0);
        
        // 建立每個單詞的位掩碼
        for (int i = 0; i < n; ++i) {
            for (char c : words[i]) {
                mask[i] |= 1 << (c - 'a');
            }
        }
        
        int maxLen = 0;
        // 兩兩比較
        for (int i = 0; i < n - 1; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if ((mask[i] & mask[j]) == 0) {
                    maxLen = max(maxLen, 
                        static_cast<int>(words[i].size() * words[j].size()));
                }
            }
        }
        return maxLen;
    }
};

總結

位掩碼技巧將字元集合操作轉化為極快的位運算，是解決此類「字元無重疊」問題的經典優化手法。實作時注意：

1. 正確計算位偏移量 c - 'a'。
2. 使用 | 累積設定位元，& 檢查重疊。
3. 雙重迴圈可從 i+1 開始避免重複檢查。

此解法在 LeetCode 實測中表現優異，時間複雜度 O(n²) 在 n ≤ 10³ 規模下完全可接受。