Redirecting to
NADOS


  Prev   Next

Number of Valid Words







Just decide; what's it's gonna be, who you're gonna be and how you're gonna do it, and then from that point, the universe will get out of your way.

Number of Valid Words

Welcome Back Reader!

In this article we will discuss the next problem based on "Bit Manipulation" i.e. Number of Valid Words.

We can get some hint from the name of the question that we have to count the number of valid words. But yes, that's not enough for solving the problem. So let's understand the problem

Before you move any further, it is advised that you give this problem a fair try. Let's jump to the problem.

Importan Link : Problem Link, Question Video Link, Solution Video Link

Understanding the problem:

In this problem you are given N number of words and M number of puzzles in the form of strings. For a given puzzle, a word is valid if both the following conditions are confirmed:

  • Condition 1 -> Word contains the first letter of the puzzle.
  • Condition 2 -> For each letter in word, that letter should be present in the puzzle.

All you need to do is to print the number of valid words corresponding to a puzzle.



Sample Input: 7
aaaa asas able ability actt actor access
6
aboveyz abrodyz abslute absoryz actresz gaswxyz

Sample Output:
aboveyz -> 1
abrodyz -> 1
abslute -> 3
absoryz -> 2
actresz -> 4
gaswxyz -> 0

How?

  • First we check the condition-1, which says that the words should contain the first letter of the word.
  • Therefore we mark the word tick if it satisfies the condition-1 for the corresponding puzzle. And if it does not; we mark a cross on that word. The words with a tick on them are eligible to get condition 2 checked.
    • img
  • Then we check the condition-2, which says for each letter of the word, that letter should be present in the puzzle.
  • Therefore we mark the word tick if it satisfies the condition-2 for the corresponding puzzle. And if it does not; we mark a cross on that word. For the result, we need the count of valid words.
  • We count the words, corresponding to each puzzle, which satisfy both the conditions and those words are basically which satisfy condition-2 as well.

For better understanding of the question, watch this part of the video lecture. Use recursion as suggested in the video.

Moving On:

Let us consider another example to understand the problem better::

Puzzles -> hidcjb, bgjic, afiehbj, cghfe
Words -> bcgi, dihj, hiba, cegh, jbaf
Output:
hidcjb -> 1 [hidj]
bgjic -> 1 [bcgi]
afiehbj -> 2 [hiba, jbaf]
cghfe -> 1 [cegh]

  • The brute force solution would deal with traversing the entire puzzles array within in traverse for entire words array and every word and puzzle firstly check whether the word contains puzzle.charAt(0)
  • And if true then check whether the puzzle contains every letter of the word if true then update a result array.
  • In the brute force approach for every puzzle we need to check for every word and then check whether it contains puzzle.charAt(0) or not.
  • This step can be avoided by taking a map that has keys from 'a' to 'z' that represents all the words that contain these letters.
  • This step ensures that we only need to check for that key that matches with the puzzle.charAt(0), hence it avoids traversing the entire word array every time.

The map for the above example will look like this: a -> hiba, jbaf
b -> bcgi, hiba, jbaf
c -> bcgi, cegh
d -> dihj
e -> cegh
f -> jbaf
g -> bcgi, cegh
h -> dihj, hiba, cegh
i -> bcgi, dihj, hiba
j -> jbaf, dihj

For more clarity of this optimized approach, watch this part of the video.

  • So to check for puzzle 'afiehbj' we only need to check elements [hiba, jbaf] and then compare.
  • Now for comparison we will make use of bit manipulation where we will build a mask for patterns and words.
  • While creating the map instead of pushing words (as shown above) we will push its corresponding mask.
  • Thereafter when comparing pattern with word mask from the map we will make a mask for pattern and then if and only if patternMask & wordMask == wordMask, this would imply that the pattern contains all the letters of the word and hence we would increment the count.
    • img
  • This step eases our comparison task as it uses bit manipulation which is memory and time-efficient.

For better understanding of bit masking, watch this part of the video.

Lets try code this!

public static ArrayList< Integer> findNumOfValidWords(String[] words, String[] puzzles) { HashMap < Integer, List< Integer>> map = new HashMap<>(); ArrayList< Integer> res = new ArrayList<>(); for (int i = 0; i < 26; i++) { map.put(i, new ArrayList<>()); } for (String word : words) { int temp = 0; //make bit mask of every word for (char c : word.toCharArray()) { temp = temp | (1 << (c - 'a' )); } //jo jo bit on hai uske saamne word rkh diya for (int i=0; i < 26; i++) { if ((temp & (1 << i)) !=0) { map.get(i).add(temp); } } } for (String p : puzzles) { int temp = 0; //make bit mask of a puzzle for (char c : p.toCharArray()) { temp = temp | (1 << (c - 'a' )); } //bring out the first character int c=p.charAt(0) - 'a' ; int count=0; for (int key : map.get(c)) { if ((key & temp)==key) { count++; } } res.add(count); } return res; } 

                                            java;
                                            true";
                                            

                                
                                            

                                                
 Yes! that looks alright.

                                                
For more clarity of the code, watch this part of the video.

                                                

                                                    
                                                

                                            

                                
                                            

                                                
Complexities:
                                                

                                                

                                                    Time Complexity
                                                

                                
                                                

                                                    

                                                        O(p*w*I)
                                                    

                                                

                                                
Space Complexity

                                                

                                                    

                                                        O(w)
                                                    

                                                

                                            

                                
                                            
Complete Code:

                                
                                            

                                                

                                                    import java.io.*;
                                                    import java.util.*;
                                
                                                    public class Main {
                                
                                                    public static void main(String[] args) {
                                                    Scanner scn = new Scanner(System.in);
                                                    int n = scn.nextInt();
                                                    String[] words = new String[n];
                                                    for(int i = 0 ; i < words.length; i++) { words[i]=scn.next(); } int m=scn.nextInt(); String[]
                                                        puzzles=new String[m]; for(int i=0 ; i < m ;i++) { puzzles[i]=scn.next(); } ArrayList< Integer>
                                                        ans = findNumOfValidWords(words,puzzles);
                                                        for(int i = 0 ; i < m; i++){ System.out.println(puzzles[i] + " -> " + ans.get(i)); } } public
                                                            static ArrayList< Integer> findNumOfValidWords(String[] words, String[] puzzles) {
                                                            HashMap< Integer, List< Integer>> map = new HashMap<>();
                                                            ArrayList< Integer> res = new ArrayList<>();
                                                                    for (int i = 0; i < 26; i++) { map.put(i, new ArrayList<>());
                                                                        }
                                                                        for (String word : words) {
                                                                        int temp = 0;
                                                                        //make bit mask of every word
                                                                        for (char c : word.toCharArray()) {
                                                                        temp = temp | (1 << (c - 'a' )); } //jo jo bit on hai uske saamne word rkh diya
                                                                            for (int i=0; i < 26; i++) { if ((temp & (1 << i)) !=0) {
                                                                            map.get(i).add(temp); } } } 
                                                                                for (String p : puzzles) {
                                                                                int temp = 0;
                                                                                //make bit mask of a puzzle
                                                                                for (char c : p.toCharArray()) {
                                                                                temp = temp | (1 << (c - 'a' )); } //bring out the first character 
                                                                                int c=p.charAt(0) - 'a' ; int count=0; for (int key : map.get(c)) { if
                                                                                    ((key & temp)==key) { count++; } } res.add(count); } return res; } }
                                                                                    

                                                                                    
                                                                

                                                                                    java;
                                                                                    true";
                                                

                                
                                                

                                                    

                                                        We hope that this article was helpful. If somehow you
                                                        are finding it difficult to understand this problem then
                                                        we advise you to watch our
                                                            video lecture of this
                                                        problem.
                                                    

                                
                                                    
Trust me it will just get easier to understand after you
                                                        have watched the solution video.

                                                    
You can contact us via our website. Doubts, suggestions
                                                        and feedback are always welcomed.

                                                    
It is also advised that you follow the sequence of
                                                        modules and questions which is there on our
                                                        website.
                                                    

                                                    
Keep practicing more and more problems daily. Meditate
                                                        enough on each step of each problem.
                                                    

                                
                                                

                                
                                                

                                                    
Number of Valid Words
                                                    

                                
                                                

                                                

                                                    
Author:
                                                        Nikita
                                                            Aggarwal
                                                    

                                                

                                                
                                                

                                                

                                                    

                                                    

                                                

                                
                                            

                                            
                                            
                                            
                                            
                                            
                                        

                                    

                                

                                            
                                
                        

            

        

    



   

   

       

           

               

                   
               

               

                   
 
               

   
   
               

   
                   

                       

                         
                       

                       

                         
                        
                         
                         
                         
                       

                       

                         

                           
                           Run
                         

                       

                       
                       
                                       

               

               

                   
                       
                   
               

   
           

           

               

   
   
               

                   

                       
                       
                   

               

   
               

   
                   

                       
                           

                               Id
                               Name