專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

最近關于數字馬力毀意向這件事在牛客網頻頻出現，原因就是數字馬力發出的offer接受率高于預期，導致剩余缺口不多。那些OC過的可能收不到offer了，OC是什么意思呢？Offer Call簡稱OC，當面試官決定錄用求職者后，HR會通過電話聯系的方式詢問求職者是否接受Offer，口頭的形式，不是正式的書面offer。

雖然不是書面offer，但你之前Offer Call的時候給別人說打算錄用你了，準備給你發offer了，而現在突然又不發了，這就叫毀意向。我們知道如果發了書面offer在返回是違法的，但這種口頭承諾的offer，后面又不發了，到底違不違法？不管違不違法，反正是不得人心的。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第318題：最大單詞長度乘積。

問題描述

來源：LeetCode第318題

難度：中等

給你一個字符串數組 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且這兩個單詞不含有公共字母。如果不存在這樣的兩個單詞，返回 0 。

示例1：

輸入：words = ["abcw","baz","foo","bar","xtfn","abcdef"] 輸出：16 解釋：這兩個單詞為 "abcw", "xtfn"。

示例2：

輸入：words = ["a","ab","abc","d","cd","bcd","abcd"] 輸出：4 解釋：這兩個單詞為 "ab", "cd"。

• 2 <= words.length <= 1000

• 1 <= words[i].length <= 1000

• words[i] 僅包含小寫字母

問題分析

這題是讓找出兩個單詞長度的最大乘積，并且這兩個單詞不能有公共的字母。計算單詞長度的乘積比較簡單，這里的關鍵點是怎么判斷兩個字符串是否有公共的字母。

因為提示中說了字符串僅包含小寫字母，小寫字母總共有26個，所以我們可以使用位運算來判斷。對于每一個字符串都可以使用一個int類型的數字來標記，從右往左第一位是 a，第二位是 b ……，出現了哪個字母就在相應的位置標記為 1 。

如果兩個數字通過與運算（&）結果為 0 ，說明這兩個字符串沒有公共的字母，可以計算它兩長度的乘積，最后只需要保留最大乘積即可。

JAVA：

public int maxProduct(String[] words) {     int length = words.length;     // 記錄每個字符串中有哪些字母     int[] bits = new int[length];     int ans = 0;     for (int i = 0; i < length; i++) {         // 標記當前字符串有哪些字母         for (char ch : words[i].toCharArray())             bits[i] |= 1 << (ch - 'a');         // 如果當前字符串和之前的字符串沒有公共的字母，就計算他們的         // 乘積，保留最大值即可。         for (int j = 0; j < i; j++) {             // 如果結果為0，表示他們沒有公共的字母             if ((bits[i] & bits[j]) == 0)                 ans = Math.max(ans, (words[i].length() * words[j].length()));         }     }     return ans; }

C++：

public:     int maxProduct(vector

  &words) {         int length = words.size();         // 記錄每個字符串中有哪些字母         vector

  bits(length);         int ans = 0;         for (int i = 0; i < length; i++) {             // 標記當前字符串有哪些字母             for (char &ch: words[i])                 bits[i] |= 1 << (ch - 'a');             // 如果當前字符串和之前的字符串沒有公共的字母，就計算他們的             // 乘積，保留最大值即可。             for (int j = 0; j < i; j++) {                 // 如果結果為0，表示他們沒有公共的字母                 if ((bits[i] & bits[j]) == 0)                     ans = max(ans, int(words[i].size() * words[j].size()));             }         }         return ans;     }

Python：

def maxProduct(self, words: List[str]) -> int:     length = len(words)     # 記錄每個字符串中有哪些字母     bits = [0] * length     ans = 0     for i in range(0, length):         # 標記當前字符串有哪些字母         for ch in words[i]:             bits[i] |= 1 << (ord(ch) - ord('a'))         # 如果當前字符串和之前的字符串沒有公共的字母，就計算他們的         # 乘積，保留最大值即可。         for j in range(0, i):             # 如果結果為0，表示他們沒有公共的字母             if (bits[i] & bits[j]) == 0:                 ans = max(ans, len(words[i]) * len(words[j]))     return ans

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。