LeetCode 916. Word Subsets
原题链接在这里:https://leetcode.com/problems/word-subsets/
题目:
We are given two arrays A
and B
of words. Each word is a string of lowercase letters.
Now, say that word b
is a subset of word a
if every letter in b
occurs in a
, including multiplicity. For example, "wrr"
is a subset of "warrior"
, but is not a subset of "world"
.
Now say a word a
from A
is universal if for every b
in B
, b
is a subset of a
.
Return a list of all universal words in A
. You can return the words in any order.
Example 1:
Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["e","o"]
Output: ["facebook","google","leetcode"]
Example 2:
Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["l","e"]
Output: ["apple","google","leetcode"]
Example 3:
Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["e","oo"]
Output: ["facebook","google"]
Example 4:
Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["lo","eo"]
Output: ["google","leetcode"]
Example 5:
Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["ec","oc","ceo"]
Output: ["facebook","leetcode"]
Note:
1 <= A.length, B.length <= 10000
1 <= A[i].length, B[i].length <= 10
A[i]
andB[i]
consist only of lowercase letters.- All words in
A[i]
are unique: there isn'ti != j
withA[i] == A[j]
.
题解:
String a in A, if it is universal for every b in B, it must cover all the letters and max corresponding multiplicity in B.
Thus construct a map to maintain all letters and max corresponding multiplicity in B.
Then for each A, if it could cover this map, then add it to the res.
Time Complexity: O(m*n + p*q). m = A.length. n = average length of string in A. p = B.length. q = average length of string in B.
Space: O(1).
AC Java:
class Solution {
public List<String> wordSubsets(String[] A, String[] B) {
List<String> res = new ArrayList<>();
if(A == null || A.length == 0){
return res;
} if(B == null || B.length == 0){
return Arrays.asList(A);
} int [] map = new int[26];
for(String b : B){
int [] bMap = new int[26];
for(char c : b.toCharArray()){
bMap[c - 'a']++;
} for(int i = 0; i<26; i++){
map[i] = Math.max(map[i], bMap[i]);
}
} for(String a : A){
int [] aMap = new int[26];
for(char c : a.toCharArray()){
aMap[c-'a']++;
} boolean isNotSubSet = false;
for(int i = 0; i<26; i++){
if(aMap[i] < map[i]){
isNotSubSet = true;
break;
}
} if(!isNotSubSet){
res.add(a);
}
} return res;
}
}
最新文章
- mysql 5.5 修改字符编码
- kafka java实例
- wiki-editor语法
- SKLabelNode类
- java.lang.class.getResource
- Emacs经常使用快捷键的注意事项
- C#托付和事件
- openstack controller ha测试环境搭建记录(一)——操作系统准备
- ORACLE 12C 基础
- 无法启动 IIS Express Web 服务器
- 关于position:fixed;的居中问题
- [Java] Java读取Word文档
- Linux Ubuntu从零开始部署web环境及项目 -----部署项目 (三)
- p2p项目,自己期望太高了。
- ●BZOJ 4008 [HNOI2015]亚瑟王
- 补习系列(6)- springboot 整合 shiro 一指禅
- lightoj-1128-Greatest Parent(二分+LCA)
- [转]IIS 日志记录时间和实际时间 不一样
- es5中for...in 和es6中 for..of遍历
- 51Nod 1668 非010串
热门文章
- ASP.NET Core MVC的Razor视图中,使用Html.Raw方法输出原生的html
- Redis高级功能-1、高并发基本概述
- java 基础 四种权限修饰符
- 一张图看懂SharpCamera
- C# LINQ干掉for循环
- 如何在ppt全屏演示时仍然显示任务栏?
- [其它]iOS 13 正式版发布 iPhone 6s或更新型号均可升级
- MAC OS系统替换brew.npm, pip 使用阿里云的镜像源
- Matlab访问者模式
- android如何在标题栏设置返回返回图标返回到另一个activity