Last Updated: 8 Feb, 2021

Ninja And Sentences

Moderate

Asked in company

Solve now

Problem statement

Ninja is trying to create a robot, which would talk to humans. Ninja is stuck at a particular phase where he wants the robot to create all possible sentences from a 2D array of words. Help Ninja in solving this problem. For a given 2D array of words, your task is to create all possible sentences that can be made using them.

Note :

In a particular sentence, the robot can use a single word from the row that the word is part of.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.
Then the T test cases follow.

The first line of each test case contains two integers ‘N’ and ‘M’ , the rows and columns of the 2D array that contains the list of words. 
The next ‘N’ lines contain ‘M’ strings each.

Output format:

For each test case, all the possible sentences formed are printed in a separate line.
The output of each test case is printed in a separate line.

Note:

The output format is predefined for this question. You need to store all possibly created sentences in a predefined data structure. Keep in mind that first you need to store all the sentences that start with the first word of the first row and so on. 

For further clarification on the same see the below example:

1
2 2 
you we
sleep drink

In this case there are more than one correct ways to store the sentences but order of the output matters so, you should keep in mind that you start with the first row and the first column and so on. 

Correct Output:             
you sleep
you drink
we sleep
we drink

Incorrect outputs:

we sleep        we drink        you drink
we drink        we sleep        you sleep
you sleep       you drink       we drink
you drink       you sleep       we sleep

Constraints :

1 <= T <= 5
1 <= N <= 5
1 <= M <= 5
1 <= W <=20
where ‘T’ is the number of test cases,  ‘N’ and ‘M’ are the dimensions of the words array, ‘array[i][j]’ is the value of words of the array, and ‘W’ denotes the size of the word.

Solve now

Approaches

01 Approach

We will use the basic idea of depth-first traversal in order to solve this problem. We create an output array to store the created sentence. We now start by considering all the words of the first row as the starting points for sentences and store them in the output array.

Let us look at the below example:

Arr = you we

have are

sleep read

Steps:

Output array = [‘you’] - store the current element
Check if it belongs to the last row => No
Recursively call the next row.
Output array = [‘you’ ‘have’] - store the current element
Again Check if it belongs to the last row => No
Recursively call the next row.
Output array = [‘you’ ‘have’ ‘ sleep’] - store the current element
Again Check if it belongs to the last row ⇒ Yes
Print the output array => you have sleep
Continue for rest words.

Algorithm:

We start with the first word of the first row, store it in the output array as the starting point of the sentence.
Now, we check if it belongs to the last row:
- If Yes
  - We simply print the words stored in the output array.
- If No
  - We recursively call the next row.
  - Store the current element as the next element of the output array
  - Continue until it is the last row.
  - Print the output array

Solve now