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 · 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