Facebook Pixel

1258. Synonymous Sentences

MediumUnion FindArrayHash TableStringBacktracking
Leetcode Link

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:

  1. Building the Union-Find structure:

    • We start by initializing a Union-Find instance uf to handle synonyms grouping. Each word in the list of synonyms 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 containing a and b, effectively stating that they are in the same synonym group.

  2. Creating structures for synonym look-up:

    • A dictionary d maps each word to a unique index (words[i] to i), 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.

  3. 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.

  4. 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 in sentence.
    • For each word:
      • If the word is not a synonym (not in d), it's added to the current path t 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 recursive dfs call, and backtracking (removing the word from t) after the call returns.
    • When the end of the sentence is reached, the joined path t is added to the list of possible sentences ans.

  5. Handling the initial call and returning the result:

    • The dfs function is called initially with i=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.

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 Evaluator

Example 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