今天是堅持每日一題打卡的第二十二天

---

題目鏈接：https://leetcode-cn.com/problems/maximum-product-of-word-lengths/

---

題解匯總：https://zhanglong.blog.csdn.net/article/details/121071779

---

題目描述

給定一個字符串數(shù)組 words，找到 length(word[i]) * length(word[j]) 的最大值，并且這兩個單詞不含有公共字母。你可以認為每個單詞只包含小寫字母。如果不存在這樣的兩個單詞，返回 0。

示例 1:
輸入: [“abcw”,“baz”,“foo”,“bar”,“xtfn”,“abcdef”]
輸出: 16
解釋: 這兩個單詞為 “abcw”, “xtfn”。

示例 2:
輸入: [“a”,“ab”,“abc”,“d”,“cd”,“bcd”,“abcd”]
輸出: 4
解釋: 這兩個單詞為 “ab”, “cd”。

示例 3:
輸入: [“a”,“aa”,“aaa”,“aaaa”]
輸出: 0
解釋: 不存在這樣的兩個單詞。

提示：
2 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] 僅包含小寫字母

---

核心思路： 位運算 + 字符串
由于字母只有26位，因此可以采用或運算的方式求出每個單詞中字母出現(xiàn)的位置和次數(shù)

同時，如果兩個數(shù)相與為0，則代表這兩個字符串無字母重復(fù)。

class Solution { private:static const int MAX_LEN = 1000 + 10; public:int maxProduct(vector<string>& words) {int arr[MAX_LEN] = {0}, pos = 0;int res = 0;for (int i = 0; i < words.size(); i++) {int t = 0;for (auto j : words[i]) {t = t | (1 << (j-'a'));}arr[pos++] = t;}for (int i = 0; i < pos; i++) {for(int j = i + 1; j < pos; j++) {if ((arr[i] & arr[j]) == 0) res = max(res, int(words[i].size() * words[j].size()));}}return res;} };

總結(jié)

以上是生活随笔為你收集整理的C++题解-Leecode 318. 最大单词长度乘积——Leecode每日一题系列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。