Domain 2MediumMEDIUM

Synonymous Sentences

Build a synonym graph using BFS/DFS to identify connected components, then use backtracking to generate all sentence variations based on component members at each word position, finally sorting the results lexicographically.

Domain: medium•Updated: 2026-09-13
#Graph#Backtracking#Sorting

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

  1. Graph Construction: Create an adjacency list from the synonyms pairs to represent equivalence relationships. Since synonymy is symmetric (undirected), add edges for both directions.
  2. 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 synonyms are treated as having only themselves as an option.
  3. 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.
  4. Sorting: Collect all generated strings in a result list and sort them lexicographically before returning.

Complexity Analysis

  • Time Complexity: O(S+V⋅E+Klog⁡K)O(S + V \cdot E + K \log K), where SS is number of synonym pairs (graph build), VV is unique words involved, EE edges for traversal to find components (KK combinations). The dominant factor is generating and sorting the output list. Given constraints (N≤10N \le 10, sentence length ≤10\le 10), this fits well within time limits.
  • Space Complexity: O(V+E)O(V + E) for graph storage, plus O(K⋅W)O(K \cdot W) to store generated sentences where KK is result count and WW 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 synonyms is empty or contains no pairs relevant to text words, every word remains