LeetCode - Word Subsets

时间:2022-01-03 15:26:41
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] and B[i] consist only of lowercase letters.
All words in A[i] are unique: there isn't i != j with A[i] == A[j].

这道题的核心就是理解对于B的处理:

先来理解题目,题目强调的是单个字母,不存在字母顺序问题,所以只要统计出B中每个小写字母,在所有的单词中出现次数最高的那个数(例如,B = ["loo","eo"],那么o 最大的出现次数为2, 因为在"loo"出现了两次,在"eo"出现了一次,所以以最大的为准),然后再统计A中的每个单词中的每个字母出现的次数,与其对比即可。
具体思路:
(1)先统计出数组B中每个小写字母的最大出现次数,因为是题目只包含26个小写字母,所以,可以直接转换成数组来保存。(这这个过程中,可以用字典或者hash来保存,这样可能会更快一些)
(2)然后,依次统计A中的没单词中每个字母的出现个数,与(1)统计的结果做对比,选择出通用单词即可。
原文:https://blog.csdn.net/xx_123_1_rj/article/details/82992861

class Solution {
public List<String> wordSubsets(String[] A, String[] B) {
List<String> resList = new ArrayList<>();
int[] temp = null;
if(A == null || B == null || A.length == 0 || B.length == 0){
return resList;
}
int[] max = new int[26];
for(String b : B){
temp = new int[26];
for(char c : b.toCharArray()){
temp[c-'a']++;
}
for(int i = 0; i< 26; i++){
if(temp[i] > max[i]){
max[i] = temp[i];
}
}
}
for(String a : A){
temp = new int[26];
for(char c : a.toCharArray()){
temp[c-'a']++;
}
for(int i = 0; i< 26; i++){
if(temp[i] < max[i]){
break;
}
if(i == 25){
resList.add(a);
}
}
}
return resList;
} }