# 1258. Synonymous Sentences¶

• Time: $O(2^n)$
• Space: $O(2^n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 class Solution { public: vector generateSentences(vector>& synonyms, string text) { set ans; unordered_map> graph; queue q{{text}}; for (const vector& synonym : synonyms) { const string& s = synonym[0]; const string& t = synonym[1]; graph[s].push_back(t); graph[t].push_back(s); } while (!q.empty()) { const string u = q.front(); q.pop(); ans.insert(u); vector words = split(u); for (string& word : words) { const auto it = graph.find(word); if (it == graph.cend()) continue; for (const string& synonym : it->second) { // Replace words[i] with its synonym. word = synonym; const string newText = join(words, ' '); if (!ans.count(newText)) q.push(newText); } } } return {ans.begin(), ans.end()}; } private: vector split(const string& s) { vector words; istringstream iss(s); for (string token; iss >> token;) words.push_back(token); return words; } string join(const vector& words, char c) { string joined; for (int i = 0; i < words.size(); ++i) { joined += words[i]; if (i != words.size() - 1) joined += c; } return joined; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution { public List generateSentences(List> synonyms, String text) { Set ans = new TreeSet<>(); Map> graph = new HashMap<>(); Queue q = new ArrayDeque<>(Arrays.asList(text)); for (List synonym : synonyms) { final String s = synonym.get(0); final String t = synonym.get(1); graph.putIfAbsent(s, new ArrayList<>()); graph.putIfAbsent(t, new ArrayList<>()); graph.get(s).add(t); graph.get(t).add(s); } while (!q.isEmpty()) { final String u = q.poll(); ans.add(u); String[] words = u.split("\\s"); for (int i = 0; i < words.length; ++i) for (final String synonym : graph.getOrDefault(words[i], new ArrayList<>())) { // Replace words[i] with its synonym. words[i] = synonym; final String newText = String.join(" ", words); if (!ans.contains(newText)) q.offer(newText); } } return new ArrayList<>(ans); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 from sortedcontainers import SortedSet class Solution: def generateSentences(self, synonyms: List[List[str]], text: str) -> List[str]: ans = SortedSet() graph = collections.defaultdict(list) q = collections.deque([text]) for s, t in synonyms: graph[s].append(t) graph[t].append(s) while q: u = q.popleft() ans.add(u) words = u.split() for i, word in enumerate(words): for synonym in graph[word]: # Replace words[i] with its synonym. words[i] = synonym newText = ' '.join(words) if newText not in ans: q.append(newText) return list(ans)