Synonymous Sentences
Problem statement
Given synonym pairs and a sentence text, return every sentence you can form by replacing each word with itself or a synonym. Choose a replacement separately for each word position. Synonyms work in both directions and through chains: if a is a synonym of b, and b is a synonym of c, any of these three words can replace either of the others.
Return each distinct sentence once, in lexicographic ascending order. The unchanged sentence is included. All words contain lowercase English letters, and the input sentence uses exactly one space between adjacent words and no leading or trailing spaces.
Function
generateSentences(synonyms: String[][], text: String) → String[]Examples
Example 1
synonyms = [["happy","joy"],["sad","sorrow"]]text = "happy sad"return = ["happy sad","happy sorrow","joy sad","joy sorrow"]The two word positions choose their synonyms independently.
Example 2
synonyms = [["a","b"],["b","c"]]text = "a"return = ["a","b","c"]Transitivity makes c a replacement for a.
Example 3
synonyms = []text = "stay calm"return = ["stay calm"]Words absent from the pairs remain unchanged.
Constraints
0 <= synonyms.length <= 30; each pair contains two words.- Every word has
1..20lowercase English letters;texthas1..10words. - At most
2000distinct output sentences are possible.