- Difficulty: Medium
- Tags: LeetCode, Medium, Union Find, Array, Hash Table, String, Backtracking, leetcode-1258, O(p * l * log(p * l)), O(p * l)
Problem
You are given a list of equivalent string pairs synonyms where synonyms[i] = [si, ti] indicates that si and ti are equivalent strings. You are also given a sentence text.
Return all possible synonymous sentences sorted lexicographically.
Example 1:
Input: synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]], text = "I am happy today but was sad yesterday" Output: ["I am cheerful today but was sad yesterday","I am cheerful today but was sorrow yesterday","I am happy today but was sad yesterday","I am happy today but was sorrow yesterday","I am joy today but was sad yesterday","I am joy today but was sorrow yesterday"]
Example 2:
Input: synonyms = [["happy","joy"],["cheerful","glad"]], text = "I am happy today but was sad yesterday" Output: ["I am happy today but was sad yesterday","I am joy today but was sad yesterday"]
Constraints:
0 <= synonyms.length <= 10synonyms[i].length == 21 <= si.length, ti.length <= 10si != titextconsists of at most10words.- All the pairs of
synonymsare unique. - The words of
textare separated by single spaces.