Last Updated: 1 Apr, 2021

Ninja and words magic

Moderate

Asked in companies

Solve now

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?.

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

Solve now

Approaches

01 Approach

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:

Declare a HashSet ‘WORDS_SET’ in which we will store all the words of the ‘WORDS’.
Declare a variable ‘ANSWER’ in which we store the resultant sentence.
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’.
Finally, return ‘ANSWER’.

Solve now