Number Of Valid Words

  Prev   Next

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. You are given N number of words.
2. You are given M puzzles in the form of M strings.
3. For a given puzzle, a word is valid if both the following conditions are confirmed - 
    Condition 1 -> Word contains the first letter of puzzle.
    Condition 2 -> For each letter in word, that letter should be present in puzzle.
4. You have to print the number of valid words corresponding to a puzzle.
Input Format 
A number N
N space separated strings
A number M
M space separated strings
Output Format 
Check the sample ouput and question video.
Question Video
Constraints 
1 <= N <= 10^5
4 <= length of word <= 50
1 <= M <= 10^4
length of puzzle string = 7
puzzle string doesn't contain any repeated characters.
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


  • Editorial

    The problem here deals with finding the number of valid words for the corresponding puzzle. Here we are provided with a list of puzzles and a list of words, we need to check for every puzzle the number of words from the list which satisfies the following criteria:

    1. Word must contain the first letter of the puzzle.

    2. The puzzle must contain all the letters of the word.

    Let us consider an example to understand the problem better,

    Patterns -> 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 pattern array within in traverse for entire words array and every word and pattern firstly check whether the word contains pattern.charAt(0) and if true then check whether the pattern contains every letter of the word if true then update a result array.

    In the brute force approach for every pattern we need to check for every word and then check whether it contains pattern.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 pattern.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

    So to check for 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 built 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. This step eases our comparison task as it uses bit manipulation which is memory and time-efficient.

    Time Complexity: O(p*w*l)

    The time complexity for the function is number of puzzles(p) * number of words(w) * max length of puzzle (l).

    Space Complexity: O(w)

    The space complexity for the function is linear as we have implemented a map and a set for storing masked words from the word array.

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name