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
- Synonyms are symmetric and transitive, so group them with union-find.
- For each group, collect all words and sort them so the generated sentences come out in lexicographic order.
- Split the text into words; each word maps either to its synonym group (sorted) or to a single-element list of itself.
- 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~bandb~cimpliesa~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.