Ninja and words magic

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
3 upvotes
Asked in companies
BarclaysMedia.netGoogle inc

Problem statement

Ninja has been given a dictionary of words ‘WORDS’ of length ‘N’ and a sentence ‘SENTENCE’ consisting of words separated by a single space. Ninja has to make the ‘SENTENCE’ as small as possible by performing the below operation any number of times.

Ninja can replace a word of the ‘SENTENCE’ with a word present in the ‘WORDS’ if and only if the prefix of that word is present in the ‘WORDS’.

Note: If the word of the ‘SENTENCE’ can be replaced by more than one word present in the ‘WORDS’, then replace it with the smallest possible word present in the ‘WORDS’.

Example for all prefixes of a string:

String ‘STR’ = “abcd” 
Then all possible prefix of this ‘STR’ are:
"a", "ab", "abc", "abcd".

Note:

1. All the words in the ‘WORDS’ and the ‘SENTENCE’ contain only lower case English alphabets.
2. ‘SENTENCE’ does not have any leading and trailing spaces.

Can you help Ninja to make the ‘SENTENCE’ as small as possible by performing the given operation?.

Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line of input contains an integer ‘T’ which denotes the number of test cases or queries to be run.

The first line of each test case will contain an integer ‘N’ representing the number of words in the ‘WORDS’.

The second line of each test case will contain ‘N’ single space-separated strings representing the words in the ‘WORDS’.

The third line of each test case will contain a string that represents the ‘SENTENCE’.
Output Format : 
For each test case, print a single line containing string denoting the ‘SENTENCE’ after making it as small as possible by performing the given operation.

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints: 
1 <= ‘T’ <= 100
1 <= ‘N’ <= 100
‘WORDS[ i ]’ = {a to z}
1 <= | ‘SENTENCE’ | <= 100000

Where ‘T’ denotes the total number of test cases, ‘N’ represents the number of words in the ‘WORDS’, and | ‘SENTENCE’ | denotes the length of the ‘SENTENCE’.

Time Limit: 1 second
Sample Input 1:
2 
3
ram shyam mohan
where is raman mohan babu 
3
a b c
add ball cat
Sample Output 1:
where is ram mohan babu
a b c

Explanation for Sample Output 1:

For sample test case 1: 


In the ‘SENTENCE’ = “where is raman mohan babu”
We can replace the word “raman” to “ram” because “ram” is the prefix of “raman’  and the prefix is present in ‘WORDS’.

So after this ‘SENTENCE’ is : “where is ram mohan babu”

For sample test case 2: 
In the ‘SENTENCE’ =  “add ball cat”
We can replace the word “add” to ‘a’ , “ball” to ‘b’ and “cat” to ‘c’ because ‘a’, ‘b’ and ‘c’ is prefixes of “add” ,”ball” and “cat” respectively and all these prefixes are present in ‘WORDS’.
So after performing this operation ‘SENTENCE’ is : a a b c
Sample Input 2:
2
4
s ss sss ssss
s ss naresh saharan baba
4
a m b
apple mango banana orange
Sample Output 2:
s s naresh s baba
a m b orange

Explanation for Sample Output 2:

For sample test case 1: 
The ‘SENTENCE’ = “s ss naresh saharan baba”.
After replacing words with their prefixes if prefixes are present in ‘WORDS’:
‘SENTENCE’ is : “s s naresh s baba”.

For sample test case 2: 
The ‘SENTENCE’ = “apple mango banana orange”.
After replacing words with their prefixes if prefixes are present in ‘WORDS’:
‘SENTENCE’ is: “a m b orange”.
Hint

Can you think of the solution using hashing?

Approaches (1)
Hashing

First, we will store all the words of ‘WORDS’ in a HashSet ‘WORDS_SET’ and then traverse all the words of the ‘SENTENCE’ and look for the prefix of each word present in the ‘WORDS_SET’ or not. If the prefix of the current word is present in the ‘WORDS_SET’ then replace the current word with the prefix present in the ‘WORDS_SET’. Otherwise, keep the current word as it is.

 

The Steps are as follows:

  1. Declare a HashSet ‘WORDS_SET’ in which we will store all the words of the ‘WORDS’.
  2. Declare a variable ‘ANSWER’ in which we store the resultant sentence.
  3. Iterate through the "SENTENCE". (say, iterator = 'i'):
    • Run a loop from ‘j’ = 0 to i’th word of ‘SENTENCE’:
      • ‘PREFIX’ = substring of i’th word of ‘SENTENCE’ from 0 to ‘j’.
      • If this ‘PREFIX’ is present in ‘WORDS_SET’:
        • Break
    • Append ‘PREFIX’ in ‘ANSWER’.
  4. Finally, return ‘ANSWER’.
Time Complexity

O(|SENTENCE|) where |‘SENTENCE’| represents the length of the ‘SENTENCE’.

 

Because we are traversing to the ‘SENTENCE’ and for each word, we are checking the prefix of the current word present in ‘WORDS_SET’ or not. Checking a word present in ‘WORDS_SET’ takes O(1) time. Hence, the overall time complexity will be O(|SENTENCE|).

Space Complexity

O(max(N, |SENTENCE| )) where ‘N’ represents the number of words in ‘WORDS’and |‘SENTENCE’| represents the length of the ‘SENTENCE’.

 

Because we are using the set ‘WORDS_SET’ for storing all the words of the ‘WORDS’. Then we are storing the resultant sentence in ‘ANSWER’.

Code Solution
(100% EXP penalty)
Ninja and words magic
Full screen
Console