新手如何给自己的网站做优化,群辉wordpress阿里云ssl,用名字做头像是什么网站,iis2008如何做网站318. 最大单词长度乘积
难度#xff1a;中等
题目
给你一个字符串数组 words #xff0c;找出并返回 length(words[i]) * length(words[j]) 的最大值#xff0c;并且这两个单词不含有公共字母。如果不存在这样的两个单词#xff0c;返回 0 。
示例 1#xff1a;
输入…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。示例 3
输入words [a,aa,aaa,aaaa]
输出0
解释不存在这样的两个单词。提示
2 words.length 10001 words[i].length 1000words[i] 仅包含小写字母
个人题解
思路
为了得到最大单词长度乘积遍历字符串数组 words 中的每一对单词判断这一对单词是否有公共字母如果没有公共字母则用这一对单词的长度乘积更新最大单词长度乘积。对上述情况剪枝只有长度乘积更大的才需要判断是否有公共字母
class Solution {// 入口public int maxProduct(String[] words) {int max 0;int len words.length;for (int i 0; i len; i) {for (int j i 1; j len; j) {if (words[i].length() * words[j].length() max !hasRepeatChar(words[i], words[j])) {max words[i].length() * words[j].length();}}}return max;}public boolean hasRepeatChar(String s1, String s2) {int s1Len s1.length();int s2Len s2.length();HashSetCharacter hashSet new HashSet(Math.min(s1Len, 26));for (int i 0; i s1Len; i) {hashSet.add(s1.charAt(i));}for (int i 0; i s2Len; i) {if (hashSet.contains(s2.charAt(i))) {return true;}}return false;}
}官方题解
方法一位运算
如果可以将判断两个单词是否有公共字母的时间复杂度降低到 O(1)则可以将总时间复杂度降低到 O(n^2)。可以使用位运算预处理每个单词通过位运算操作判断两个单词是否有公共字母。由于单词只包含小写字母共有 26 个小写字母因此可以使用位掩码的最低 26 位分别表示每个字母是否在这个单词中出现。将 a 到 z 分别记为第 0 个字母到第 25 个字母则位掩码的从低到高的第 i 位是 1 当且仅当第 i 个字母在这个单词中其中 0 i 25。
用数组 masks 记录每个单词的位掩码表示。计算数组 masks 之后判断第 i 个单词和第 j 个单词是否有公共字母可以通过判断 mask[i] mask[j] 是否等于 0 实现当且仅当 mask[i] mask[j] 0 时第 i 个单词和第 j 个单词没有公共字母此时使用这两个单词的长度乘积更新最大单词长度乘积。
class Solution {public int maxProduct(String[] words) {int length words.length;int[] masks new int[length];for (int i 0; i length; i) {String word words[i];int wordLength word.length();for (int j 0; j wordLength; j) {masks[i] | 1 (word.charAt(j) - a);}}int maxProd 0;for (int i 0; i length; i) {for (int j i 1; j length; j) {if ((masks[i] masks[j]) 0) {maxProd Math.max(maxProd, words[i].length() * words[j].length());}}}return maxProd;}
}复杂度分析
时间复杂度O(L n^2)其中L是数组 words 中的全部单词长度之和n是数组 words 的长度空间复杂度O(n)n是数组 words 的长度。需要常见长度为 n 的位掩码数组 masks
方法二位运算优化
方法一需要对数组 words 中的每个单词计算位掩码如果数组 words 中存在由相同的字母组成的不同单词则会造成不必要的重复计算。例如单词 mcct 和 mct 包含的字母相同只是字母的出现次数和单词长度不同因此这两个单词的位掩码表示也相同。由于判断两个单词是否有公共字母是通过判断两个单词的位掩码的按位与运算实现因此在位掩码相同的情况下单词的长度不会影响是否有公共字母当两个位掩码的按位与运算等于 0 时为了得到最大单词长度乘积这两个位掩码对应的单词长度应该尽可能大。根据上述分析可知如果有多个单词的位掩码相同则只需要记录该位掩码对应的最大单词长度即可。
可以使用哈希表记录每个位掩码对应的最大单词长度然后遍历哈希表中的每一对位掩码如果这一对位掩码的按位与运算等于 0 则用这一对位掩码对应的长度乘积更新最大单词长度乘积。
由于每个单词的位掩码都不等于 0 任何一个不等于 0 的数和自身做按位与运算的结果一定不等于 0 因此当一对位掩码的按位与运算等于 0 时这两个位掩码一定是不同的对应的单词也一定是不同的。
class Solution {public int maxProduct(String[] words) {MapInteger, Integer map new HashMapInteger, Integer();int length words.length;for (int i 0; i length; i) {int mask 0;String word words[i];int wordLength word.length();for (int j 0; j wordLength; j) {mask | 1 (word.charAt(j) - a);}if (wordLength map.getOrDefault(mask, 0)) {map.put(mask, wordLength);}}int maxProd 0;SetInteger maskSet map.keySet();for (int mask1 : maskSet) {int wordLength1 map.get(mask1);for (int mask2 : maskSet) {if ((mask1 mask2) 0) {int wordLength2 map.get(mask2);maxProd Math.max(maxProd, wordLength1 * wordLength2);}}}return maxProd;}
}复杂度分析
时间复杂度O(L n ^ 2)空间复杂度O(n)
作者力扣官方题解 链接https://leetcode.cn/problems/maximum-product-of-word-lengths/solutions/1104441/zui-da-dan-ci-chang-du-cheng-ji-by-leetc-lym9/ 来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
