单词子集
我们给出两个单词数组 A 和 B。每个单词都是一串小写字母。
现在，如果 b 中的每个字母都出现在 a 中，包括重复出现的字母，那么称单词 b是单词 a 的子集。 例如，“wrr” 是 “warrior” 的子集，但不是 “world” 的子集。
如果对 B 中的每一个单词 b，b 都是 a 的子集，那么我们称 A 中的单词 a 是通用的。
你可以按任意顺序以列表形式返回 A 中所有的通用单词。
示例 1：
输入：A = ["amazon","apple","facebook","google","leetcode"], B = ["e","o"]
输出：["facebook","google","leetcode"]
class Solution {
public List<String> wordSubsets(String[] A, String[] B) {
int[]isValid=new int[A.length];
for(int i=0;i<B.length;i++){
String b=B[i];
//int []arrInit=new int[26];
for(int h=0;h<A.length;h++){
if(isValid[h]==-1)
continue;;
int[]arr=new int[26];
for(int j=0;j<b.length();j++)
arr[b.charAt(j)-'a']++;
String a=A[h];
// System.out.print(arr['e'-'a']+" ");
for(int j=0;j<a.length();j++){
if(arr[a.charAt(j)-'a']>0)
arr[a.charAt(j)-'a']--;
}
// System.out.print(arr['e'-'a']+" ");
for(int m=0;m<26;m++)
if(arr[m]>0){
isValid[h]=-1;
}
if(isValid[h]!=-1)
isValid[h]++;
// System.out.println(isValid[h]);
}
}
List<String>re=new ArrayList<String>();
for(int i=0;i<A.length;i++){
if(isValid[i]==B.length)
re.add(A[i]);
}
return re;
}
}这段代码超时了，毕竟A,B的长度都10000了，复杂度怎么着也有10^8
优化一下之后通过
class Solution {
public List<String> wordSubsets(String[] A, String[] B) {
int arrInit[]=new int[26];
for(int i=0;i<B.length;i++){
int []arrTmp=new int[26];
String b=B[i];
for(int j=0;j<b.length();j++)
arrTmp[b.charAt(j)-'a']++;
for(int j=0;j<26;j++){
arrInit[j]=Math.max(arrTmp[j],arrInit[j]);
}
}
//System.out.println(arrInit['e'-'a']+" "+arrInit['o'-'a']);
int[]isValid=new int[A.length];
for(int i=0;i<A.length;i++){
int arr[]=new int[26];
System.arraycopy(arrInit,0,arr,0,26);
String a=A[i];
for(int j=0;j<a.length();j++){
if(arr[a.charAt(j)-'a']>0)
arr[a.charAt(j)-'a']--;
}
// System.out.print(arr['e'-'a']+" ");
for(int m=0;m<26;m++)
if(arr[m]>0){
isValid[i]=-1;
break;
}
// System.out.println(isValid[i]);
}
List<String>re=new ArrayList<String>();
for(int i=0;i<A.length;i++){
if(isValid[i]==0)
re.add(A[i]);
}
return re;
}
}