1258. Synonymous Sentences
Problem Description
The problem is centered around finding all possible sentences that can be formed by using synonyms of words in a given sentence. Given is a list of pairs of words, synonyms
, where each pair represents two words that are synonymous, which means they can be used interchangeably without changing the meaning of the sentence. Additionally, we are provided with a string text
that represents a sentence. Our task is to generate all unique sentences that can be formed by replacing words in the text
with their synonyms, as per the synonyms
list provided. The sentences should be returned in a lexicographically sorted order—meaning, sorted alphabetically as they would appear in a dictionary.
Flowchart Walkthrough
To determine the correct algorithm for solving LeetCode problem 1258, "Synonymous Sentences," let's utilize the algorithm flowchart to guide our decision-making process.
Here's a detailed explanation step-by-step:
Is it a graph?
- No: Although the problem involves synonymous pairs, it does not specifically involve nodes and connections as typical graph problems do. It's more about generating sentences which are synonymous.
Need to solve for kth smallest/largest?
- No: The problem is not focused on ordering or ranking elements (e.g., finding the kth smallest/largest); instead, it involves generating possible combinations.
Involves Linked Lists?
- No: The structure of the problem doesn't use or involve linked lists.
Does the problem have small constraints?
- Yes: The problem involves generating all possible synonymous sentences based on a given set of synonyms. The constraints are typically small because there are a limited number of synonyms and sentences to evaluate. This allows for deeper nested operations without performance concerns.
Brute force / Backtracking?
- Yes: Since the problem requires generating all possible combinations of synonymous sentences, backtracking is a suitable method. This method will allow exploring different word choices at various sentence positions, reverting choices if they don't lead to new valid sentences, and exploring further possibilities.
Conclusion: Based on the steps taken through the flowchart, the problem of generating synonymous sentences when given lists of synonyms leans towards a backtracking approach. This method is suitable because it facilitates the comprehensive exploration of word choices, which is necessary to enumerate all possible synonymous sentences.
Intuition
To find all possible synonymous sentences, we need to think about grouping synonyms together and then combinatorically creating sentences. The core steps involved are union-finding synonyms, creating synonymous groups, and then recursively generating sentences.
To facilitate the connection between synonyms, a Union-Find data structure is an ideal choice. With Union-Find, we can efficiently merge sets of synonyms and quickly find the representative synonym for each set (the root of the set). Therefore, in the context of this problem, two words are considered in the same set if they are direct synonyms or are connected through a chain of synonym pairs.
Then, we utilize Depth First Search (DFS) to build up sentences from the available words. Using DFS allows us to explore all possible combinations of synonyms in the text. More specifically, for each word in the text
, we check if it has synonyms by looking it up in a dictionary that we've built of synonym sets. If a word has synonyms, we will have to iterate over each synonym, add it to the current sentence, and then recursively call DFS on the rest of the sentence. If a word does not have any synonyms, we simply append it to the current sentence and move on to the next word.
Lastly, since we need to return the sentences in lexicographically sorted order, the synonyms within each set are kept sorted. This ensures that as we build the sentences recursively, we are adding synonyms in the lexicographically smallest order at each step, and thus we generate the overall list of sentences in a sorted manner.
Keeping the Union-Find for efficient querying and merging, using a dictionary for fast synonym look-up, employing DFS for complete sentence generation, and ensuring synonyms are sorted within their sets collectively lead us to a comprehensive solution to generate all possible synonymous sentences.
Learn more about Union Find and Backtracking patterns.
Solution Approach
The solution approach involves using a Union-Find data structure for grouping synonyms and a Depth First Search (DFS) algorithm for generating all possible sentences. Here's how the solution is implemented:
-
Building the Union-Find structure:
- We start by initializing a Union-Find instance
uf
to handle synonyms grouping. Each word in the list ofsynonyms
is given a unique index, and these indices are used within the Union-Find data structure. - For each synonym pair
(a, b)
, we perform a union operation. This merges the sets containinga
andb
, effectively stating that they are in the same synonym group.
- We start by initializing a Union-Find instance
-
Creating structures for synonym look-up:
- A dictionary
d
maps each word to a unique index (words[i]
toi
), allowing for quick access to their corresponding set representative. - We build a graph
g
which maps each root (representative of a synonym group) to a list of indices corresponding to the members of that synonym group.
- A dictionary
-
Sorting the synonyms:
- We ensure each synonym group in
g
is sorted lexicographically by their word representation using the words from our words list. This is crucial for maintaining the sorting of the final sentences.
- We ensure each synonym group in
-
Generating sentences with DFS:
- The
dfs
function is a recursive call that builds sentences word by word. We split the original sentence using spaces and then iterate through each word insentence
. - For each word:
- If the word is not a synonym (not in
d
), it's added to the current patht
and the recursive call proceeds to the next word. - If the word is a synonym, we find its corresponding root and iterate over all the words in that synonym group, appending each one to
t
, moving to the next word with a recursivedfs
call, and backtracking (removing the word fromt
) after the call returns.
- If the word is not a synonym (not in
- When the end of the
sentence
is reached, the joined patht
is added to the list of possible sentencesans
.
- The
-
Handling the initial call and returning the result:
- The
dfs
function is called initially withi=0
, signaling the start of sentence generation. - Once all DFS calls are complete, we return the
ans
list, which now contains all possible sentences sorted lexicographically, as our answer.
- The
By the end of this process, we have effectively navigated through all potential sentences that could be formed by swapping out synonyms. The Union-Find structure efficiently grouped synonyms, and the DFS algorithm exhaustively explored all combinations to produce a comprehensive set of sentences.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider the sentence: "happy joyous" and the list of synonyms [["happy", "cheerful"], ["joyous", "blissful"]]
. We want to create all possible unique sentences using the synonyms provided.
Step 1: Building the Union-Find structure
- Initialize Union-Find
uf
. - "happy" is unioned with "cheerful" (both words are now in the same set).
- "joyous" is unioned with "blissful" (both words are now in the same set).
Step 2: Creating structures for synonym look-up
- Build a dictionary mapping:
d = { "happy": 0, "cheerful": 1, "joyous": 2, "blissful": 3 }
. - Construct a graph
g
that will map the indices of the root synonyms to their group members.
Step 3: Sorting the synonyms
- Sort the groups so that synonyms are in lexicographic order. Now,
g
would have "cheerful" listed before "happy" and "blissful" before "joyous".
Step 4: Generating sentences with DFS
- Begin with the first word "happy". It has a synonym "cheerful". We have two paths to follow now; one with "happy" and the other with "cheerful".
- Next word "joyous" also has a synonym "blissful". For each path we had, we'll now create two more paths – one with "joyous" and the other with "blissful".
- Following every path there are now four possible sentences.
- "happy joyous"
- "happy blissful"
- "cheerful joyous"
- "cheerful blissful"
Step 5: Handling the initial call and returning the result
- Start the
dfs
algorithm by processing the first word. - All unique combinations have been explored, and the list
ans
consists of the four sentences listed above. - Return the sorted
ans
:["cheerful blissful", "cheerful joyous", "happy blissful", "happy joyous"]
.
Each step of the Union-Find and DFS process ensures the generation of all potential synonymous sentences. Our initial sentence, through synonym substitution, resulted in four lexicographically sorted unique sentences as the final output.
Solution Implementation
1from collections import defaultdict
2from itertools import chain
3
4class UnionFind:
5 def __init__(self, size):
6 self.parent = list(range(size)) # initialize parent array
7 self.group_size = [1] * size # initialize group sizes
8
9 def find(self, x):
10 # Find root of x with path compression
11 if self.parent[x] != x:
12 self.parent[x] = self.find(self.parent[x])
13 return self.parent[x]
14
15 def union(self, a, b):
16 # Merge groups that a and b belong to
17 parent_a, parent_b = self.find(a), self.find(b)
18 if parent_a != parent_b:
19 # Union by size - smaller group joined to larger group
20 if self.group_size[parent_a] > self.group_size[parent_b]:
21 self.parent[parent_b] = parent_a
22 self.group_size[parent_a] += self.group_size[parent_b]
23 else:
24 self.parent[parent_a] = parent_b
25 self.group_size[parent_b] += self.group_size[parent_a]
26
27
28class Solution:
29 def generateSentences(self, synonyms, text):
30 def dfs(index):
31 # If the end of the sentence is reached, add to the answer
32 if index >= len(sentence_pieces):
33 answers.append(' '.join(temp_sentence))
34 return
35 # If the word is not a synonym, add as is and continue
36 if sentence_pieces[index] not in synonyms_index:
37 temp_sentence.append(sentence_pieces[index])
38 dfs(index + 1)
39 temp_sentence.pop()
40 else:
41 # If the word is a synonym find all possible synonyms and recurse
42 root = union_find.find(synonyms_index[sentence_pieces[index]])
43 for j in grouped_synonyms[root]:
44 temp_sentence.append(all_words[j])
45 dfs(index + 1)
46 temp_sentence.pop()
47
48 # Flatten and deduplicate word list from synonyms
49 all_words = list(set(chain.from_iterable(synonyms)))
50 synonyms_index = {word: index for index, word in enumerate(all_words)}
51 union_find = UnionFind(len(synonyms_index))
52
53 # Union synonyms pairs
54 for a, b in synonyms:
55 union_find.union(synonyms_index[a], synonyms_index[b])
56
57 # Group synonyms
58 grouped_synonyms = defaultdict(list)
59 for i in range(len(all_words)):
60 grouped_synonyms[union_find.find(i)].append(i)
61
62 # Sort synonyms in lexicographic order
63 for synonym_root in grouped_synonyms:
64 grouped_synonyms[synonym_root].sort(key=lambda i: all_words[i])
65
66 # Initialize for DFS
67 sentence_pieces = text.split()
68 answers = []
69 temp_sentence = []
70
71 # Begin DFS
72 dfs(0)
73 return answers
74
1import java.util.*;
2
3class UnionFind {
4 private int[] parent; // parent[i] holds the parent of i in the UF structure
5 private int[] size; // size[i] holds the size of the tree rooted at i
6
7 // Constructor initializes each element's parent to itself and size to 1
8 public UnionFind(int n) {
9 parent = new int[n];
10 size = new int[n];
11 for (int i = 0; i < n; ++i) {
12 parent[i] = i;
13 size[i] = 1;
14 }
15 }
16
17 // find method with path compression, returns the root of the set x belongs to
18 public int find(int x) {
19 if (parent[x] != x) {
20 parent[x] = find(parent[x]);
21 }
22 return parent[x];
23 }
24
25 // Union method to merge sets containing a and b
26 public void union(int a, int b) {
27 int rootA = find(a);
28 int rootB = find(b);
29 if (rootA != rootB) {
30 // Merge smaller tree into the larger one
31 if (size[rootA] > size[rootB]) {
32 parent[rootB] = rootA;
33 size[rootA] += size[rootB];
34 } else {
35 parent[rootA] = rootB;
36 size[rootB] += size[rootA];
37 }
38 }
39 }
40}
41
42class Solution {
43 private List<String> answers = new ArrayList<>(); // List of all possible sentences
44 private List<String> currentSentence = new ArrayList<>(); // Holds the current sentence during DFS
45 private List<String> uniqueWords; // List of unique words across all synonyms
46 private Map<String, Integer> wordIdMap; // Maps word to its index
47 private UnionFind unionFind; // Union-Find instance for grouping synonyms
48 private List<Integer>[] synonymGroups; // Holds groups of synonym indices
49 private String[] originalSentence; // Original sentence split by whitespace
50
51 // Main method to generate all possible sentences given a list of synonyms and a text string
52 public List<String> generateSentences(List<List<String>> synonyms, String text) {
53 Set<String> setOfSynonyms = new HashSet<>(); // Set to ensure unique words are collected
54 for (List<String> pairs : synonyms) {
55 setOfSynonyms.addAll(pairs);
56 }
57 uniqueWords = new ArrayList<>(setOfSynonyms);
58 int wordCount = uniqueWords.size();
59 wordIdMap = new HashMap<>(wordCount);
60
61 // Populate the wordIdMap with each unique word's index
62 for (int i = 0; i < uniqueWords.size(); ++i) {
63 wordIdMap.put(uniqueWords.get(i), i);
64 }
65
66 unionFind = new UnionFind(wordCount);
67 // Perform union operations for all pairs of synonyms
68 for (List<String> pairs : synonyms) {
69 unionFind.union(wordIdMap.get(pairs.get(0)), wordIdMap.get(pairs.get(1)));
70 }
71
72 // Initialize synonym groups
73 synonymGroups = new List[wordCount];
74 Arrays.setAll(synonymGroups, k -> new ArrayList<>());
75 for (int i = 0; i < wordCount; ++i) {
76 synonymGroups[unionFind.find(i)].add(i);
77 }
78 // Sort groups alphabetically based on the represented words
79 for (List<Integer> group : synonymGroups) {
80 group.sort((i, j) -> uniqueWords.get(i).compareTo(uniqueWords.get(j)));
81 }
82
83 // Split the original text into words
84 originalSentence = text.split(" ");
85 // Start DFS to build possible sentences
86 dfs(0);
87 return answers;
88 }
89
90 // Helper method to perform DFS and generate all possible sentences
91 private void dfs(int index) {
92 if (index >= originalSentence.length) {
93 answers.add(String.join(" ", currentSentence));
94 return;
95 }
96 // If current word has synonyms
97 if (wordIdMap.containsKey(originalSentence[index])) {
98 // Iterate through all synonyms
99 for (int synonymIndex : synonymGroups[unionFind.find(wordIdMap.get(originalSentence[index]))]) {
100 currentSentence.add(uniqueWords.get(synonymIndex));
101 dfs(index + 1);
102 currentSentence.remove(currentSentence.size() - 1);
103 }
104 } else {
105 // No synonym for current word, add it as is
106 currentSentence.add(originalSentence[index]);
107 dfs(index + 1);
108 currentSentence.remove(currentSentence.size() - 1);
109 }
110 }
111}
112
1#include <vector>
2#include <string>
3#include <unordered_set>
4#include <unordered_map>
5#include <numeric>
6#include <iostream>
7#include <sstream>
8#include <algorithm>
9#include <functional>
10
11using namespace std;
12
13// The UnionFind class is a data structure that provides efficient union and find operations.
14class UnionFind {
15public:
16 // Constructor initializes the union-find structure for n elements.
17 UnionFind(int n) {
18 parent = vector<int>(n);
19 rank = vector<int>(n, 1);
20 iota(parent.begin(), parent.end(), 0); // Fill with consecutive integers.
21 }
22
23 // Unites two subsets into a single subset.
24 void unite(int a, int b) {
25 int parentA = find(a), parentB = find(b);
26 if (parentA != parentB) {
27 // Union by rank heuristic: attach the smaller tree to the root of the larger tree.
28 if (rank[parentA] > rank[parentB]) {
29 parent[parentB] = parentA;
30 rank[parentA] += rank[parentB];
31 } else {
32 parent[parentA] = parentB;
33 rank[parentB] += rank[parentA];
34 }
35 }
36 }
37
38 // Finds the representative of the set that element x is a part of.
39 int find(int x) {
40 if (parent[x] != x) {
41 parent[x] = find(parent[x]); // Path compression heuristic.
42 }
43 return parent[x];
44 }
45
46private:
47 vector<int> parent, rank; // Parent links and ranks of the trees.
48};
49
50class Solution {
51public:
52 // This function generates all possible sentences by substituting synonyms in the given text.
53 vector<string> generateSentences(vector<vector<string>>& synonyms, string text) {
54 unordered_set<string> synonymSet;
55 // Insert all synonyms into a set to remove duplicates.
56 for (auto& pair : synonyms) {
57