Skip to content

Latest commit

 

History

History
108 lines (89 loc) · 2.81 KB

README.md

File metadata and controls

108 lines (89 loc) · 2.81 KB

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].

Solutions (Ruby)

1. Solution

# @param {String[]} a# @param {String[]} b# @return {String[]}defword_subsets(a,b)count=[0] * 26b.eachdo |sub| count_=count_chars(sub)(0...26).eachdo |i| count[i]=[count[i],count_[i]].maxendenda.filter{ |word| count_chars(word).zip(count).all?{ |c| c[0] >= c[1]}}end# @param {String} s# @return {Integer[]}defcount_chars(s)count=[0] * 26s.each_byte{ |c| count[c - 97] += 1}countend

Solutions (Rust)

1. Solution

implSolution{pubfnword_subsets(a:Vec<String>,b:Vec<String>) -> Vec<String>{letmut count = [0;26];for sub in b {let count_ = Self::count_chars(&sub);for i in0..26{ count[i] = count[i].max(count_[i]);}} a.into_iter().filter(|word| {Self::count_chars(&word).iter().zip(count.iter()).all(|(x, y)| x >= y)}).collect()}fncount_chars(s:&str) -> [i32;26]{letmut count = [0;26];for c in s.bytes(){ count[(c - b'a')asusize] += 1;} count }}
close