[LC] 318. Maximum Product of Word Lengths
2024-09-07 00:01:24
Given a string array words
, find the maximum value of length(word[i]) * length(word[j])
where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.
Example 1:
Input:["abcw","baz","foo","bar","xtfn","abcdef"]
Output:16
The two words can be
Explanation:"abcw", "xtfn"
.
Example 2:
Input:["a","ab","abc","d","cd","bcd","abcd"]
Output:4
The two words can be
Explanation:"ab", "cd"
.
Example 3:
Input:["a","aa","aaa","aaaa"]
Output:0
No such pair of words.
Explanation:
class Solution {
public int maxProduct(String[] words) {
int[] checker = new int[words.length];
if (words == null || words.length == 0) {
return 0;
}
int res = 0; for (int i = 0; i < words.length; i++) {
String word = words[i];
for (int j = 0; j < word.length(); j++) {
char curChar = word.charAt(j);
checker[i] |= 1 << curChar - 'a';
}
} for (int i = 0; i < words.length - 1; i++) {
for (int j = i + 1; j < words.length; j++) {
if ((checker[i] & checker[j]) == 0) {
res = Math.max(res, words[i].length() * words[j].length());
}
}
}
return res;
}
}
public class Solution {
public int largestProduct(String[] dict) {
// Write your solution here
Arrays.sort(dict, new Comparator<String>(){
@Override
public int compare(String a, String b) {
return b.length() - a.length();
}
});
int[] arr = new int[dict.length];
for (int i = 0; i < dict.length; i++) {
for (int j = 0; j < dict[i].length(); j++) {
arr[i] |= 1 << dict[i].charAt(j) - 'a';
}
}
int res = 0;
for (int i = 1; i < dict.length; i++) {
for (int j = 0; j < i; j++) {
if (dict[i].length() * dict[j].length() <= res) {
break;
}
if ((arr[i] & arr[j]) == 0) {
res = dict[i].length() * dict[j].length();
}
}
}
return res;
}
}
最新文章
- C# HttpHelper 采集
- iOS-分段控制器-基本概念
- LINUX重启MYSQL的命令
- Mysql or Mongodb LBS快速实现方案
- InstallShield: Component-Feature Associations
- Wix 安装部署(一)同MSBuild 自动生成打包文件 转
- CF402E Strictly Positive Matrix 传递闭包用强连通分量判断
- c语言学习
- $(obj).data() 绑定和获取数据的应用
- 【编译原理】语法分析LL(1)分析法的FIRST和FOLLOW集
- 04737_C++程序设计_第10章_面向对象设计实例
- 把vim变成C编辑器
- python 第三方库下载
- Django之路:模型(数据库)和自定义Field以及数据表的更改
- 201521123055 《Java程序设计》第4周学习总结
- WebBrowser加载一个URL被多次调用DocumentCompleted 的问题解决方案<;转>;
- BZOJ3737 : [Pa2013]Euler
- 内存管理-slab[代码]
- 设计模式之Strategy(策略)(转)
- wxPython的使用--类似画板的界面