合肥建设干部学校网站首页,加我vx看,网站建设 工单,北京建筑有限公司【LetMeFly】318.最大单词长度乘积
力扣题目链接#xff1a;https://leetcode.cn/problems/maximum-product-of-word-lengths/
给你一个字符串数组 words #xff0c;找出并返回 length(words[i]) * length(words[j]) 的最大值#xff0c;并且这两个单词不含有公共字母。如…【LetMeFly】318.最大单词长度乘积
力扣题目链接https://leetcode.cn/problems/maximum-product-of-word-lengths/
给你一个字符串数组 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。
示例 3
输入words [a,aa,aaa,aaaa]
输出0
解释不存在这样的两个单词。提示
2 words.length 10001 words[i].length 1000words[i] 仅包含小写字母
方法一模拟
对于一个单词字符串我们可以使用一个整数二进制下的低26位代表这个单词中出现过的字母。这个整数的低 i i i位代表字母 i i i是否出现过。
这样对于两个单词是否有相同的字母我们只需要看这两个单词对应的整数与运算的结果是否为 0 0 0即可。
时间复杂度 O ( n 2 × L ) O(n^2\times L) O(n2×L)其中 n l e n ( w o r d s ) nlen(words) nlen(words)空间复杂度 O ( n ) O(n) O(n)
方法二模拟哈希表小优化
方法一中我们需要遍历每一个单词对应的整数以观察二者是否有相同的字母。
方法二中的小优化是使用哈希表存储整数 m a s k mask mask对应单词的最大长度。复杂度不变但是对于出现的字母相同的所有单词只会存储一次。
时间复杂度 O ( n 2 × L ) O(n^2\times L) O(n2×L)其中 n l e n ( w o r d s ) nlen(words) nlen(words)空间复杂度 O ( n ) O(n) O(n)
AC代码
C
class Solution {
private:int genMask(string s) {int ans 0;for (char c : s) {ans | (1 (c - a));}return ans;}
public:int maxProduct(vectorstring words) {unordered_mapint, int ma;int ans 0;for (string s : words) {int mask genMask(s);int length s.size();for (auto [thatMask, thatLength] : ma) {if (!(mask thatMask)) {ans max(ans, length * thatLength);}}ma[mask] max(ma[mask], length);}return ans;}
};Python
# from typing import List
# from collections import defaultdictclass Solution:def genMask(self, s: str) - int:ans 0for c in s:ans | (1 (ord(c) - ord(a)))return ansdef maxProduct(self, words: List[str]) - int:ma defaultdict(int)ans 0for s in words:mask, length self.genMask(s), len(s)for key, val in ma.items():if not key mask:ans max(ans, val * length)ma[mask] max(ma[mask], length)return ans同步发文于CSDN原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/134254146
