Synonymous Sentences

01 · Question

You are given a list of equivalent string pairs synonyms where synonyms[i] = [s_i, t_i] indicates that s_i and t_i are equivalent strings. You are also given a sentence text.

Return all possible synonymous sentences sorted lexicographically.

02 · Analysis

Build synonym connected components first: equivalence is transitive, so a pair lookup alone is insufficient. At each word position choose any word in its component, keeping unchanged words as singleton choices. DFS enumerates the Cartesian product, and sorting the final sentences enforces lexicographic output. If S sentences of length at most L are produced, materialization costs O(SL) and sorting can cost O(SL log(S+1)), in addition to graph preprocessing.

03 · Solution

Reference solution

1import collections
2
3class Solution:
4    def generateSentences(self, synonyms: List[List[str]], text: str) -> List[str]:
5        graph = collections.defaultdict(list)
6        for u, v in synonyms:
7            graph[u].append(v)
8            graph[v].append(u)
9
10        def get_synonyms(word):
11            q = collections.deque([word])
12            visited = set([word])
13            res = []
14            while q:
15                node = q.popleft()
16                res.append(node)
17                for nei in graph[node]:
18                    if nei not in visited:
19                        visited.add(nei)
20                        q.append(nei)
21            return sorted(res)
22
23        words = text.split()
24        res = []
25
26        def backtrack(i, current):
27            if i == len(words):
28                res.append(" ".join(current))
29                return
30
31            if words[i] not in graph:
32                current.append(words[i])
33                backtrack(i + 1, current)
34                current.pop()
35            else:
36                for syn in get_synonyms(words[i]):
37                    current.append(syn)
38                    backtrack(i + 1, current)
39                    current.pop()
40
41        backtrack(0, [])
42        return sorted(list(set(res)))

Stepping Numbers