Synonymous Sentences
Asked at Rippling
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.
Asked At
| 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.
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
from 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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