Formatted question description: https://leetcode.ca/all/916.html
916. Word Subsets (Medium)
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]
.
Related Topics:
String
Solution 1.
// OJ: https://leetcode.com/problems/word-subsets/
// Time: O((A + B) * N) where N is the maximum length of string
// Space: O(1)
class Solution {
public:
vector<string> wordSubsets(vector<string>& A, vector<string>& B) {
int N = A.size(), target[26] = {}, j = 0;
for (auto &b : B) {
int cnt[26] = {};
for (char c : b) cnt[c - 'a']++;
for (int i = 0; i < 26; ++i) target[i] = max(target[i], cnt[i]);
}
for (int i = 0; i < N; ++i) {
int cnt[26] = {};
for (char c : A[i]) cnt[c - 'a']++;
bool valid = true;
for (int k = 0; k < 26 && valid; ++k) valid = target[k] <= cnt[k];
if (valid) A[j++] = A[i];
}
A.resize(j);
return A;
}
};
Java
-
class Solution { public List<String> wordSubsets(String[] A, String[] B) { List<String> universalList = new ArrayList<String>(); int[] counts = getMaxCounts(B); for (String word : A) { int[] wordCounts = getWordCounts(word); boolean flag = true; for (int i = 0; i < 26; i++) { if (wordCounts[i] < counts[i]) { flag = false; break; } } if (flag) universalList.add(word); } return universalList; } public int[] getMaxCounts(String[] array) { int[] counts = new int[26]; for (String word : array) { int[] curCounts = new int[26]; char[] wordArray = word.toCharArray(); for (char c : wordArray) curCounts[c - 'a']++; for (int i = 0; i < 26; i++) counts[i] = Math.max(counts[i], curCounts[i]); } return counts; } public int[] getWordCounts(String word) { int[] wordCounts = new int[26]; char[] wordArray = word.toCharArray(); for (char c : wordArray) wordCounts[c - 'a']++; return wordCounts; } }
-
// OJ: https://leetcode.com/problems/word-subsets/ // Time: O((A + B) * N) where N is the maximum length of string // Space: O(1) class Solution { public: vector<string> wordSubsets(vector<string>& A, vector<string>& B) { int N = A.size(), target[26] = {}, j = 0; for (auto &b : B) { int cnt[26] = {}; for (char c : b) cnt[c - 'a']++; for (int i = 0; i < 26; ++i) target[i] = max(target[i], cnt[i]); } for (int i = 0; i < N; ++i) { int cnt[26] = {}; for (char c : A[i]) cnt[c - 'a']++; bool valid = true; for (int k = 0; k < 26 && valid; ++k) valid = target[k] <= cnt[k]; if (valid) A[j++] = A[i]; } A.resize(j); return A; } };
-
class Solution(object): def wordSubsets(self, A, B): """ :type A: List[str] :type B: List[str] :rtype: List[str] """ B = set(B) res = [] count = collections.defaultdict(int) for b in B: cb = collections.Counter(b) for c, v in cb.items(): count[c] = max(count[c], v) res = [] for a in A: ca = collections.Counter(a) isSuccess = True for c, v in count.items(): if v > ca[c]: isSuccess = False break if isSuccess: res.append(a) return res