Ninja And Sentences

Moderate
0/80
Average time to solve is 35m
profile
Contributed by
12 upvotes
Asked in company
OYO

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.
Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1:

1
2 2 
you we
sleep drink

Sample Output 1:

you sleep
you drink
we sleep
we drink

Explanation of Sample Input 1:

Taking a word from each row and adding it to each word of rest all the columns.

Sample Input 2:

2
3 1
i
love
coding
3 2
you we
have are
eat read

Sample Output 2:

i love coding
you have eat
you have read
you are eat
you are read
we have eat
we have read
we are eat
we are read
Hint

Think about using recursion

Approaches (1)
Recursion Depth First Traversal

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: 

 

  1. We start with the first word of the first row, store it in the output array as the starting point of the sentence.
  2. 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
Time Complexity

O(M^N), where N and M are the dimensions of the 2d array.

 

The algorithm will generate all possible sentences which will be M^N. So the overall time complexity will be O(M^N).

Space Complexity

O((M^N) * W), where ‘N’ and ‘W’ are the number of rows in the given array and the word size, respectively.

 

Since we are using an array to store the sentences, the overall space complexity will be O((M^N) * W).

Code Solution
(100% EXP penalty)
Ninja And Sentences
Full screen
Console