Problem Breakdown
We are given an undirected graph where nodes represent words and edges represent synonym relationships. The input text is a sequence of these words separated by spaces. For every word in the sentence, we must replace it with any word from its connected component (including itself). If a word does not appear in the synonym list, it forms a singleton component containing only itself. We need to generate all unique sentences formed by replacing each position’s word independently and return them sorted lexicographically.
Intuition
The core challenge is handling transitivity: if A ~ B and B ~ C, then A can become C directly or indirectly. This suggests treating synonyms as a graph where we find connected components (equivalence classes). For any specific word in the sentence text, all words reachable from it via synonym edges are valid replacements for that position. Since each position is independent of others regarding replacement choices, this structure allows us to use backtracking: iterate through every possible option at index i, recurse for i+1. Finally, sorting ensures the output requirement is met efficiently given the constraints on sentence length and number of synonyms.
Approach
- Graph Construction: Create an adjacency list from the
synonymspairs to represent equivalence relationships. Since synonymy is symmetric (undirected), add edges for both directions. - Component Identification: For each unique word found in the text that exists in our graph, perform a traversal (BFS or DFS) to find all words belonging to its connected component. Store these as sorted lists of options per word. Words not present in
synonymsare treated as having only themselves as an option. - Backtracking Generation: Split the text into tokens. Use recursion to build sentences index by index. At each index, iterate through all valid synonym options for that specific token and recurse. When reaching the end of the sentence (index equals length), join the list of words and add to results.
- Sorting: Collect all generated strings in a result list and sort them lexicographically before returning.
Complexity Analysis
- Time Complexity: , where is number of synonym pairs (graph build), is unique words involved, edges for traversal to find components ( combinations). The dominant factor is generating and sorting the output list. Given constraints (, sentence length ), this fits well within time limits.
- Space Complexity: for graph storage, plus to store generated sentences where is result count and is average word length (recursion stack depth proportional to sentence length).
Solution
from collections import defaultdict
from typing import List
class Solution:
def generateSentences(self, synonyms: List[List[str]], text: str) -> List[str]:
# Build adjacency list from synonym pairs
adj = defaultdict(set)
for u, v in synonyms:
adj[u].add(v)
adj[v].add(u)
# Helper to get all connected words (synonyms + self) for a given word using BFS
def get_synonym_group(word):
if word not in adj:
return [word]
visited = set()
queue = [word]
group_members = []
while queue:
curr = queue.pop(0) # Using list pop(0) is fine for small N, deque preferred but unnecessary here
if curr not in visited:
visited.add(curr)
group_members.append(curr)
for neighbor in adj[curr]:
if neighbor not in visited:
queue.append(neighbor)
return sorted(group_members)
# Split text into words to process each position independently
words = text.split()
result = []
n = len(words)
def backtrack(index, current_sentence):
if index == n:
result.append(" ".join(current_sentence))
return
word = words[index]
# Get all possible replacements for this position.
# If the word is not in our synonym graph (adj), it only has itself as an option.
options = get_synonym_group(word) if word in adj else [word]
for replacement in options:
current_sentence[index] = replacement
backtrack(index + 1, current_sentence)
# Initialize the mutable sentence list with placeholders
backtrack(0, [""] * n)
return sorted(result)
Edge Cases Handled
- Empty Synonyms: If
synonymsis empty or contains no pairs relevant to text words, every word remains