⚡Flashcard Drill➔
NeetCode #164LC-1258MediumArrays & Hashing
← Back to All Problems

#164 · #1258 · Synonymous Sentences(近义词句子)

📌 Problem Statement & Constraints

Given a list of synonym pairs and a sentence text, generate all possible sentences by replacing words with their synonyms. Return the results sorted lexicographically. Constraints: 0 <= synonyms.length <= 10, 1 <= text.length <= 10; synonym pairs are symmetric and transitive.

💡 Core Algorithmic Approaches

  1. Synonyms are symmetric and transitive, so group them with union-find.
  2. For each group, collect all words and sort them so the generated sentences come out in lexicographic order.
  3. Split the text into words; each word maps either to its synonym group (sorted) or to a single-element list of itself.
  4. The answer is the Cartesian product of those lists, joined by spaces and sorted.

💻 Benchmark Python3 Implementation

class Solution:
    def generateSentences(self, synonyms: List[List[str]], text: str) -> List[str]:
        from collections import defaultdict
        from itertools import product

        parent = {}

        def find(x: str) -> str:
            parent.setdefault(x, x)
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        for a, b in synonyms:
            ra, rb = find(a), find(b)
            if ra != rb:
                parent[ra] = rb

        groups = defaultdict(list)
        for w in parent:
            groups[find(w)].append(w)
        for g in groups.values():
            g.sort()                       # sorted -> lexicographic output

        options = []
        for w in text.split():
            if w in parent:
                options.append(groups[find(w)])
            else:
                options.append([w])        # unchanged word

        return sorted(" ".join(combo) for combo in product(*options))

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * alpha + P log P) where m is the number of synonym pairs and P is the size of the Cartesian product (bounded by the problem's small constraints).
💾 Space Complexity
O(P * L) for the output.

⚠️ Interview Pitfalls & Follow-ups

  • Ignoring transitivity: a~b and b~c implies a~c, which union-find handles but a direct pair map would not.
  • Forgetting that synonymy is symmetric: the pairs must be unioned in both directions, which union(a, b) does.
  • Not sorting the groups: the output must be lexicographically sorted, and sorting the groups first makes the Cartesian product naturally ordered.
  • Replacing words that have no synonyms: they must pass through unchanged, which the single-element list handles.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems