Java实现 LeetCode 318 最大单词长度乘积
2023-09-14 08:58:05 时间
318. 最大单词长度乘积
给定一个字符串数组 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
解释: 不存在这样的两个单词。
PS:
全是小写字母, 可以用一个32为整数表示一个word中出现的字母,
hash[i]存放第i个单词出现过的字母, a对应32位整数的最后一位,
b对应整数的倒数第二位, 依次类推. 时间复杂度O(N^2)
判断两两单词按位与的结果, 如果结果为0且长度积大于最大积则更新
class Solution {
public int maxProduct(String[] words) {
int n = words.length;
int[] wordsBit = new int[n];
for (int i = 0; i < n; i++) {
wordsBit[i] = convertWordToBit(words[i]);
}
int max = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if ((wordsBit[i] & wordsBit[j]) == 0) {
int newLength = words[i].length() * words[j].length();
max = max < newLength ? newLength : max;
}
}
}
return max;
}
private int convertWordToBit(String word) {
int wordBit = 0;
int n = word.length();
for (int i = 0; i < n; i++) {
wordBit = wordBit | (1 << (word.charAt(i) - 'a'));
}
return wordBit;
}
}
相关文章
- JAVA 注解教程(四)Java 预置的注解
- Java实现 LeetCode 779 第K个语法符号(递归)
- Java实现 LeetCode 746 使用最小花费爬楼梯(递推)
- Java实现 LeetCode 738 单调递增的数字(暴力)
- Java实现 LeetCode 713 乘积小于K的子数组(子集数量+双指针)
- Java实现 LeetCode 677 键值映射(字典树)
- Java实现 LeetCode 649 Dota2 参议院(暴力大法)
- Java实现 LeetCode 637 二叉树的层平均值(遍历树)
- Java实现 LeetCode 630 课程表 III(大小堆)
- Java实现 LeetCode 617 合并二叉树(遍历树)
- Java实现 LeetCode 606 根据二叉树创建字符串(遍历树)
- Java实现 LeetCode 541 反转字符串 II(暴力大法)
- Java实现 LeetCode 528 按权重随机选择(TreeMap)
- Java实现 LeetCode 523 连续的子数组和(ง •_•)ง
- Java实现 LeetCode 495 提莫攻击
- Java实现 LeetCode 458 可怜的小猪
- Java实现 LeetCode 449 序列化和反序列化二叉搜索树
- Java实现 LeetCode 355 设计推特
- Java实现 LeetCode 330 按要求补齐数组
- Java实现 LeetCode 316 去除重复字母
- Java实现 LeetCode 241 为运算表达式设计优先级
- Java实现 LeetCode 229 求众数 II(二)
- Java实现 LeetCode 135 分发糖果
- Java实现LeetCode 110. Balanced Binary Tree
- Java实现 LeetCode_0038_CountandSay