Synonymous Sentences

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:

1. Initialize a vector, allSentences to store all sentences. Each sentence will be stored in the form of a vector of strings.
2. 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.
3. 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]).
4. 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.
5. 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.
6. Return the vector, allSentences.

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

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

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

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

1. 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.
2. 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).

O(N^M), where N is the number of pairs of synonyms, and M is the number of words in the sentence.

In the worst case, all words in the list of synonyms can be synonyms of a single word. So, that word can have N synonyms. If all the words in the sentence are synonyms of each other, we can replace each word with its N synonyms, and since there are M words in the sentence, the time complexity becomes O(N^M).

O(N^M), where N is the number of pairs of synonyms, and M is the number of words in the sentence.

We need extra space to maintain hashmaps to store the synonyms for every word of the sentence. Since there can be N different synonyms for each word, we need extra O(N^M) space.