Number Of Valid Words
1. You are given N number of words.Input Format
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.
A number NOutput Format
N space separated strings
A number M
M space separated strings
Check the sample ouput and question video.Question Video
1 <= N <= 10^5Sample Input
4 <= length of word <= 50
1 <= M <= 10^4
length of puzzle string = 7
puzzle string doesn't contain any repeated characters.
7Sample Output
aaaa asas able ability actt actor access
6
aboveyz abrodyz abslute absoryz actresz gaswxyz
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