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:
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"]

Practice this problem on LeetCode(Click Here).

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;
                }
            }
            if(flag == 0) ans.add(tmp);
        }
        return ans;
    }
}


Other Posts You May Like
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Single Number 3 LeetCode Solution - The Coding Shala

LeetCode - Number of Good Pairs Solution - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Java Method Overloading - The Coding Shala