RUST GYM v0.2.4

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. 1 <= A.length, B.length <= 10000
  2. 1 <= A[i].length, B[i].length <= 10
  3. A[i] and B[i] consist only of lowercase letters.
  4. All words in A[i] are unique: there isn't i != j with A[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.