Home » Technical Interview Questions » String Interview Questions » Recursively print all the sentences that can be formed from list of word lists

Recursively print all the sentences that can be formed from list of word lists


Reading Time - 1 mins

Given a list of word lists, write a functions to print all possible sentences one by one by taking one word from each list

Example

INPUT
s[][] = {{“I”, “You”}, {“love”,”hate”},{“programming”}}

OUTPUT
“I love programing”
“I hate programming”
“You love programming”
“You hate Prrogramming”

Algorithm

1. Cosider every word in the first list as the first word in output sentence

2. Now, recur for remaining lists

C++ Program

#include <iostream>
#include <string>
 
#define R 3
#define C 3
using namespace std;
 

void printUtil(string arr[R][C], int m, int n, string result[R])
{
    // Add current word to result array
    result[m] = arr[m][n];
 
    // If it is the last word, then print
    if (m==R-1)
    {
        for (int i=0; i<R; i++)
        {
           cout << result[i] << " ";
        }
        cout << endl;
        return;
    }
 
    // Recur for next row
    for (int i=0; i<C; i++)
    {
       if (arr[m+1][i] != "")
       {
          printUtil(arr, m+1, i, result);
       }
    }
}
 
// Considers all words in first row and prints
void printAllSentences(string arr[R][C])
{
   // Create an array to store sentence
   string result[R];
 
   //Consider all words in first row
   for (int i=0; i<C; i++)
   {
     if (arr[0][i] != "")
     {
        printUtil(arr, 0, i, result);
     }
   }
}
 

int main()
{
   string arr[R][C]  = {{"I", "You"}, {"love","hate"},{"programming"}};
 
   printAllSentences(arr);
 
   return 0;
}

Try It

 

 

READ  Longest Common Prefix using Sorting
Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions