Is Synonymous Sentences easy or hard?

Synonymous Sentences is usually classified as a medium difficulty problem. The challenge comes from combining two ideas: grouping words using Union-Find and generating all sentence permutations using DFS or backtracking.

Synonymous Sentences Python/Java solution

A typical implementation builds a Union-Find structure for all synonym pairs, maps each root to a sorted list of words, and then runs DFS over the sentence. Python, Java, C++, and Go implementations follow the same pattern: union operations for grouping and recursive generation for sentence combinations.

How to solve Synonymous Sentences in O(n)?

Building synonym groups with Union-Find is close to linear time because each union and find operation runs in nearly O(1) amortized time. After grouping, DFS or backtracking generates sentences by iterating through synonym lists for each word position. The combination generation dominates the runtime when many substitutions exist.

What is the best approach for Synonymous Sentences?

Union-Find combined with DFS is the most efficient approach. Union-Find groups all related synonyms into connected components in near O(1) amortized time per union operation. DFS or backtracking then generates every valid sentence combination by replacing words with others from the same synonym group.

Is Synonymous Sentences asked at Google/Amazon/Meta?

Variants of synonym grouping and sentence generation appear in interviews at companies like Google, Amazon, and Meta. The problem tests knowledge of Union-Find, graph connectivity, and recursive backtracking for generating combinations.

What data structure is used in Synonymous Sentences?

Union-Find (Disjoint Set Union) is commonly used to group synonyms efficiently. A hash map stores the mapping from group root to all words in that synonym set, and DFS/backtracking generates the possible sentences. Arrays or lists store the final combinations.

What is the time complexity of Synonymous Sentences?

The Union-Find setup takes roughly O(P α(P)) where P is the number of synonym pairs and α is the inverse Ackermann function. Generating sentences depends on the number of combinations, which can grow exponentially with the number of replaceable words. Sorting synonym groups typically adds O(C log C).

Description Hints 3 Solution Video 7:21

1258. Synonymous Sentences

Medium57.2% acceptance3 companiesPremium elsewhere, free here

You are given a list of equivalent string pairs synonyms where synonyms[i] = [s_i, t_i] indicates that s_i and t_i 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 <= 10
synonyms[i].length == 2
1 <= s_i.length,t_i.length <= 10
s_i != t_i
text consists of at most 10 words.
All the pairs of synonyms are unique.
The words of text are separated by single spaces.

Asked at 3 companies

Cruise Automation Moveworks Rippling

Topics

Hints open one at a time

Hint 1

Find all synonymous groups of words.

Hint 2

Use union-find data structure.

Hint 3

By backtracking, generate all possible statements.

7:21

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[["happy","joy"],["sad","sorrow"],["joy","cheerful"]]
"I am happy today but was sad yesterday"

Input

[["happy","joy"],["cheerful","glad"]]
"I am happy today but was sad yesterday"

Your code is saved on this device.Solution