1258. Synonymous Sentences
Asked at Rippling
Difficulty
Medium
Time
O(n * m + R log R)
Space
O(n + R * m)
Pattern
Array
Companies
1
Problem
You are given a list of synonym pairs synonyms and a sentence text. Each pair [a, b] means the words a and b can be used in place of each other. This relation is transitive: if a equals b and b equals c, then all three words belong to the same group.
For every word in the sentence, you may keep it or swap it with any other word from its synonym group. Words that appear in no pair have only one choice: themselves.
Return all possible sentences you can build this way, as a list of strings, sorted in lexicographical order. Each sentence keeps the same number of words, separated by single spaces. A word that is not in any synonym pair must stay unchanged.
Words that can be swapped
Constraints
- ●
0 <= synonyms.length <= 10 - ●
synonyms[i].length == 2 - ●
1 <= si.length, ti.length <= 10 - ●
si != ti - ●
text consists of at most 10 words - ●
All the pairs of synonyms are unique - ●
The words of text are separated by single spaces
Examples
synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]], text = "I am happy today but was sad yesterday"["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 wassynonyms = [["happy","joy"],["cheerful","glad"]], text = "I am happy today but was sad yesterday"["I am happy today but was sad yesterday","I am joy today but was sad yesterday"]Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Rippling | Medium | View all Rippling questions → |
How to Think About It
Build a graph where each synonym pair is an undirected edge between words
Use Union-Find or DFS to group all words that are synonyms into connected components
For each word in the input sentence, find all words in its synonym group including itself
Use backtracking to generate all combinations by picking one word from each group
Sort the final result lexicographically before returning
Optimal Approach
Build a graph from synonym pairs and use DFS or Union-Find to find connected components (synonym groups). For each word in the input sentence, look up its group. Use backtracking to generate all sentences by recursively choosing one synonym from each word position. At each position, iterate through all words in the synonym group (including the original word) and recurse to the next position. Collect all generated sentences and sort them lexicographically. The key insight is treating synonyms as an equivalence relation that partitions words into groups.
Union-Find groups, then backtracking
What Trips People Up in Real Interviews
Clarify that synonyms are transitive (if A=B and B=C then A=C)
Ask if the output must be sorted (typically yes for this problem)
Discuss Union-Find vs DFS for building synonym groups
Mention that empty synonyms list means no replacement possible for that word
Talk about edge case where a word appears multiple times in the sentence
Solution Code
O(n * m + R log R) timefrom collections import defaultdict
class Solution:
def generateSentences(self, synonyms: list[list[str]], text: str) -> list[str]:
parent = {}
def find(x):
if x not in parent:
parent[x] = x
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def union(a, b):
ra, rb = find(a), find(b)
if ra != rb:
if ra < rb:
parent[ra] = rb
else:
parent[rb] = ra
for a, b in synonyms:
union(a, b)
groups = defaultdict(list)
for word in list(parent.keys()):
groups[find(word)].append(word)
for g in groups:
groups[g].sort()
words = text.split(' ')
result = []
def backtrack(i, current):
if i == len(words):
result.append(' '.join(current))
return
w = words[i]
root = find(w) if w in parent else w
candidates = groups.get(root, [w])
for syn in candidates:
current.append(syn)
backtrack(i + 1, current)
current.pop()
backtrack(0, [])
result.sort()
return resultFrequently Asked Questions
What is the Synonymous Sentences problem?
Given a list of synonymous word pairs and a sentence, generate all possible sentences by replacing words with their synonyms. Each synonymous group forms an equivalence class, and you must produce every valid combination by substituting words within the same group. Return the sentences sorted in lexicographical order.
How do you solve Synonymous Sentences?
The optimal approach runs in O(n * m + R log R) time and O(n + R * m) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Synonymous Sentences?
Synonymous Sentences is asked at Rippling. It is a medium difficulty problem.
What are common mistakes on Synonymous Sentences?
- Clarify that synonyms are transitive (if A=B and B=C then A=C)
- Ask if the output must be sorted (typically yes for this problem)
- Discuss Union-Find vs DFS for building synonym groups
- Mention that empty synonyms list means no replacement possible for that word
- Talk about edge case where a word appears multiple times in the sentence