乘积"/>
【每日一题】最大单词长度乘积
文章目录
- Tag
- 题目来源
- 题目解读
- 解题思路
- 方法一：转态压缩
- 写在最后
Tag
【位运算-状态压缩】【字符串】【2023-11-06】
题目来源
318. 最大单词长度乘积
题目解读
找出英文字符串数组中两个字符串长度乘积的最大值，并且这两个字符串不含公共字母。
解题思路
方法一：转态压缩
找出两个字符串长度乘积的最大值，我们可以枚举所有的字符串，判断是否不含公共字母，如果不含则更新最大的长度乘积值得到最终答案。
如何判断两个字符串是否含公共字母呢？我们可以使用 状态压缩 将字符串转化成对应的整形数字，如果两个字符串对应的整形数字按位与等于 0，说明两个字符串不存在公共字母，否则存在公共字母。关于状态压缩可以参考 位运算基础与应用。
具体地，首先维护一个数组 mask 记录每个字符串进行状态压缩后的整形数字，然后枚举所有的字符串对应的整形数字，如果两字符串对应的整形数字按位与等于零，则更新最大值。
实现代码
class Solution {
public:int maxProduct(vector<string>& words) {int n = words.size();vector<int> mask(n); // (1) 首先把每个字符串用二进制数转换得到mask[i]int i, j;for(i = 0; i < n; ++i){for(auto &c : words[i]){mask[i] |= 1 << (c - 'a');}}int mx = 0;for(i = 0; i < n; ++i){for(j = 1 + 1; j < n; ++j){ // (2) 再遍历所有情况if((mask[i] & mask[j]) == 0){mx = std::max(mx, (int)(words[i].size() * words[j].size()));}}}return mx;}
};
复杂度分析
时间复杂度： O ( n 2 ) O(n^2) O(n2)。
空间复杂度： O ( n ) O(n) O(n)。
优化
由于有的字符串含有的字符相同，但是长度不同，我们更加在意的是更长的字符串，因此可以使用一个哈希表来记录含有相同字符的字符串的最大长度，最后枚举哈希表即可，这样可以在判断最大值时少枚举几次，一定程度上降低时间复杂度。这里不给出实现代码，读者可以自行尝试。
写在最后
如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。
如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。
最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个 👍 哦。
更多推荐
【每日一题】最大单词长度乘积
发布评论