Word Subsets LeetCode Solution - The Coding Shala

Home >> LeetCode >> Word Subsets

In this post, we will learn how to solve LeetCode's Word Subsets Problem and will implement its solution in Java.

Word Subsets Problem

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 the word an 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:

Example 2:

Example 3:

Word Subsets Java Solution

Approach 1

Use the words of array B as a single word then checks with array A words. First, we count the maximum letters required to make all the words in array B. then will compare this count with array A words.

Java Program:

```class Solution {
public List<String> wordSubsets(String[] A, String[] B) {
List<String> ans = new ArrayList<>();

int[] find = new int[26];
for(String tmp : B) {
int[] count = new int[26];
for(int i=0; i<tmp.length();i++) {
count[tmp.charAt(i)-'a']++;
}
for(int i=0; i<26; i++) {
if(count[i] > find[i]) {
find[i] = count[i];
}
}
}

for(String tmp : A) {
int[] check = new int[26];
for(int i=0; i< tmp.length(); i++) {
check[tmp.charAt(i)-'a']++;
}

int flag = 0;
for(int i=0; i<26; i++){
if(check[i] < find[i]) {
flag = 1;
break;
}
}
}
return ans;
}
}
```

Other Posts You May Like