Last Updated: 16 Mar, 2021

Synonymous Sentences

Moderate

Asked in company

Solve now

Problem statement

You are given a sentence consisting of several space-separated words and a list of pairs of synonyms. Your task is to find out all possible sentences that can be formed by replacing any word in the sentence with any of its synonyms.

Note :

1. A word may or may not have synonyms.
2. There can be multiple synonyms for a single word.
3. All words only contain lowercase English letters.

Input Format :

The first line contains an integer T, which denotes the number of test cases to be run. Then, the T test cases follow. 

The first line of each test case contains two space-separated integers, N and M, denoting the number of pairs of synonyms in the list and the number of words in the sentence.

The second line contains 2*N space-separated words. For every, i from 1 to N, (2*i-1)-th and (2*i)-th words are synonyms of each other.

The third line contains M space-separated words which form the sentence.

Output Format :

For each test case, print in separate lines all sentences that can be formed by replacing one or more words with their synonyms. 

Please note that all the sentences must be printed in lexicographically sorted order.

The output of every 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 <= 10
1 <= N,M <= 8
1 <= |word| <= 10

Where |word| denotes the length of any word that appears in the sentence.

Time Limit: 1sec

Solve now

Approaches

01 Approach

The approach is to use hashing and recursion to find out different groups of words so that every word of a group is a synonym of every other word in that particular group. Now, replace every possible word with their respective synonyms one by one using recursion and when all the words for this traversal have been replaced, push this sentence into the vector and continue traversing to find all other possible sentences.

Steps:

Initialize a vector, allSentences to store all sentences. Each sentence will be stored in the form of a vector of strings.
Initialize a hashmap, unordered_map<string, set<string>> groups that will be used to find groups of all the words that are synonyms of each other. Each word will be matched with a set of words. Each word in this set can be used in place of the original word.
Run a loop for i=0 to i=synonyms.size() and do:
1. Insert second word into the set of the first word i.e. groups[i][0].insert(groups[i][1]).
2. Insert first word into the set of the second word i.e. groups[i][1].insert(groups[i][0]).
Now, run a loop for i=0 to i=sentence.size() and do:
1. Declare word = sentence[i].
2. Create a set, wordList, that will store all the synonyms for this word.
3. Call the function findSynonyms(word, wordList, groups). This will store all the synonyms of the current word.
4. Now, make groups[word] = wordList.
Now, call the function useSynonymn(sentence, groups, allSentences, 0). This function will traverse through every index, and one by one, replace all the synonyms for the word present at the current index. When the current sentence is completed, the sentence will be pushed into the vector, allSentences.
Return the vector, allSentences.

void findSynonyms(string word, set<string>& wordList, unordered_map<string, set<string>>& groups)

Insert word in the wordList.
If word is not present in the hashmap, groups, simply return from here.
Create a set temp and make temp = group[words]
Now, erase word from the hashmap.
For each string text in temp, call findSynonyms(text, wordList, groups).
Now, again make groups[word] = temp.

void useSynonym(vector<string> currentSentence, unordered_map<string, set<string>>& groups,

vector<vector<string>>& allSentences, int idx)

If all words for the current sentence have been replaced i.e if idx == sentence.size(),
1. allSentences.push_back(currentSentence).
2. Return from here.
For each string synonym in groups[sentence[idx]],
1. Replace the word at current index by the synonym i.e make currentSentence[idx] = synonym.
2. Call useSynonym(currentSentence, groups, allSentences, idx+1).

Solve now