916. 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]
.
Rust Solution
struct Solution;
impl Solution {
fn word_subsets(a: Vec<String>, b: Vec<String>) -> Vec<String> {
let mut max_count = [0; 26];
for s in b {
let mut count = [0; 26];
for b in s.bytes() {
count[(b - b'a') as usize] += 1;
}
for i in 0..26 {
max_count[i] = max_count[i].max(count[i]);
}
}
let mut res = vec![];
'a: for s in a {
let mut count = [0; 26];
for b in s.bytes() {
count[(b - b'a') as usize] += 1;
}
for i in 0..26 {
if count[i] < max_count[i] {
continue 'a;
};
}
res.push(s)
}
res
}
}
#[test]
fn test() {
let a = vec_string!["amazon", "apple", "facebook", "google", "leetcode"];
let b = vec_string!["e", "o"];
let res = vec_string!["facebook", "google", "leetcode"];
assert_eq!(Solution::word_subsets(a, b), res);
let a = vec_string!["amazon", "apple", "facebook", "google", "leetcode"];
let b = vec_string!["l", "e"];
let res = vec_string!["apple", "google", "leetcode"];
assert_eq!(Solution::word_subsets(a, b), res);
let a = vec_string!["amazon", "apple", "facebook", "google", "leetcode"];
let b = vec_string!["e", "oo"];
let res = vec_string!["facebook", "google"];
assert_eq!(Solution::word_subsets(a, b), res);
let a = vec_string!["amazon", "apple", "facebook", "google", "leetcode"];
let b = vec_string!["lo", "eo"];
let res = vec_string!["google", "leetcode"];
assert_eq!(Solution::word_subsets(a, b), res);
let a = vec_string!["amazon", "apple", "facebook", "google", "leetcode"];
let b = vec_string!["ec", "oc", "ceo"];
let res = vec_string!["facebook", "leetcode"];
assert_eq!(Solution::word_subsets(a, b), res);
}
Having problems with this solution? Click here to submit an issue on github.