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.

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of these pictures shows the visit order of a depth-first search?

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            synonymSet.insert(pair[0]);
58            synonymSet.insert(pair[1]);
59        }
60      
61        vector<string> words(synonymSet.begin(), synonymSet.end());
62        unordered_map<string, int> wordToId;
63        int n = words.size();
64        // Map each unique word to an ID.
65        for (int i = 0; i < n; ++i) {
66            wordToId[words[i]] = i;
67        }
68      
69        UnionFind unionFind(n);
70        // Unite the synonyms in the Union-Find structure.
71        for (auto& pair : synonyms) {
72            unionFind.unite(wordToId[pair[0]], wordToId[pair[1]]);
73        }
74      
75        vector<vector<int>> groups(n);
76        // Group the synonyms by their root parent.
77        for (int i = 0; i < n; ++i) {
78            groups[unionFind.find(i)].push_back(i);
79        }
80        // Sort each group of synonyms lexicographically.
81        for (int i = 0; i < n; ++i) {
82            sort(groups[i].begin(), groups[i].end(), [&](int a, int b) {
83                return words[a] < words[b];
84            });
85        }
86
87        istringstream iss(text);
88        vector<string> sentenceWords;
89        string currentWord;
90
91        // Split the text into words.
92        while (iss >> currentWord) {
93            sentenceWords.emplace_back(currentWord);
94        }
95
96        vector<string> resultSentences;
97        vector<string> tempSentence;
98
99        // Recursive function to generate all possible sentences.
100        function<void(int)> generate = [&](int i) {
101            if (i >= sentenceWords.size()) {
102                // If at the end of the sentence, join the words and add to the result.
103                string sentence = joinSentence(tempSentence);
104                resultSentences.emplace_back(sentence);
105                return;
106            }
107            if (!wordToId.count(sentenceWords[i])) {
108                // If the word isn't a synonym, add as is.
109                tempSentence.emplace_back(sentenceWords[i]);
110                generate(i + 1);
111                tempSentence.pop_back();
112            } else {
113                // If the word is a synonym, try all possible substitutions.
114                for (int id : groups[unionFind.find(wordToId[sentenceWords[i]])]) {
115                    tempSentence.emplace_back(words[id]);
116                    generate(i + 1);
117                    tempSentence.pop_back();
118                }
119            }
120        };
121
122        generate(0); // Start the recursive generation from the first word.
123        return resultSentences;
124    }
125
126private:
127    // Helper function to join words in a sentence.
128    string joinSentence(const vector<string>& words) {
129        string sentence;
130        for (int i = 0; i < words.size(); ++i) {
131            if (i > 0) {
132                sentence += " ";
133            }
134            sentence += words[i];
135        }
136        return sentence;
137    }
138};
139
1// A global map to keep track of word to ID and ID to word translation.
2const wordToId: Record<string, number> = {};
3const words: string[] = [];
4
5// Union-Find structure to help union and find word groups.
6const parent: number[] = [];
7const rank: number[] = [];
8
9// Helper function to find the representative of the set that element x is a part of.
10function find(x: number): number {
11  if (parent[x] !== x) {
12    parent[x] = find(parent[x]); // Path compression heuristic.
13  }
14  return parent[x];
15}
16
17// Function to unite two subsets into a single subset.
18function unite(a: number, b: number): void {
19  let parentA = find(a);
20  let parentB = find(b);
21  if (parentA !== parentB) {
22    // Union by rank heuristic: attach the smaller tree to the root of the larger tree.
23    if (rank[parentA] > rank[parentB]) {
24      parent[parentB] = parentA;
25      rank[parentA] += rank[parentB];
26    } else {
27      parent[parentA] = parentB;
28      rank[parentB] += rank[parentA];
29    }
30  }
31}
32
33// The main function that generates all possible sentences by substituting synonyms in the given text.
34function generateSentences(synonyms: string[][], text: string): string[] {
35  const synonymSet: Set<string> = new Set();
36
37  // Insert all synonyms into a set to remove duplicates and fill word-related structures.
38  synonyms.flat().forEach((word) => {
39    synonymSet.add(word);
40    if (!wordToId[word]) {
41      wordToId[word] = words.length;
42      words.push(word);
43      const id = words.length - 1;
44      parent[id] = id; // Initially, every word is its own parent.
45      rank[id] = 1; // Initial rank is 1.
46    }
47  });
48
49  // Unite the synonyms in the Union-Find structure.
50  synonyms.forEach(([word1, word2]) => {
51    unite(wordToId[word1], wordToId[word2]);
52  });
53
54  const groups: number[][] = Array.from({ length: words.length }, () => []);
55
56  // Group the synonyms by their root parent.
57  Object.keys(wordToId).forEach((word) => {
58    groups[find(wordToId[word])].push(wordToId[word]);
59  });
60
61  // Sort each group of synonyms lexicographically.
62  groups.forEach((group) => {
63    group.sort((a, b) => words[a].localeCompare(words[b]));
64  });
65
66  const sentenceWords: string[] = text.split(' ');
67  const resultSentences: string[] = [];
68  let tempSentence: string[] = [];
69
70  // Recursive function to generate all possible sentences.
71  const generate = (i: number) => {
72    if (i >= sentenceWords.length) {
73      // If at the end of the sentence, join the words and add to the result.
74      const sentence = tempSentence.join(' ');
75      resultSentences.push(sentence);
76      return;
77    }
78    const currentWord = sentenceWords[i];
79    if (!wordToId[currentWord]) {
80      // If the word isn't a synonym, add as is.
81      tempSentence.push(currentWord);
82      generate(i + 1);
83      tempSentence.pop();
84    } else {
85      // If the word is a synonym, try all possible substitutions.
86      const synonymsGroup = groups[find(wordToId[currentWord])];
87      synonymsGroup.forEach((id) => {
88        tempSentence.push(words[id]);
89        generate(i + 1);
90        tempSentence.pop();
91      });
92    }
93  };
94
95  generate(0); // Start the recursive generation from the first word.
96  return resultSentences;
97}
98
Not Sure What to Study? Take the 2-min Quiz：

How does quick sort divide the problem into subproblems?

Time and Space Complexity

Time Complexity

  • The initialization of the UnionFind class takes O(N) time, where N is the number of unique words in synonyms.
  • The find function has a time complexity of O(alpha(N)) per call due to path compression, where alpha is the inverse Ackermann function, which is a very slow-growing function and can be considered almost constant for all practical purposes.
  • The union function is called for each pair of synonyms, thus taking O(M * alpha(N)) time in total, where M is the number of synonym pairs.
  • Building the dictionary d requires O(N) time.
  • Constructing g involves iterating over all words and finding their root, requiring O(N * alpha(N)) time.
  • Sorting the lists in g requires O(K * log(K)) time for each list, where K is the maximum number of synonyms for a word (in the worst case K = N when all words are synonyms of each other), hence in total O(N * log(N)).
  • The dfs function is the most expensive one. It generates all combinations of synonyms, which could be O(2^L) in the worst-case scenario, where L is the length of the sentence. Each recursive call to dfs may take up to O(L) time to join and append words to form a sentence, thus the dfs has a potential time complexity of O(2^L * L).

The final time complexity is the sum of all these operations, which is dominated by the dfs function, so the overall time complexity is O(N + M * alpha(N) + N * alpha(N) + N * log(N) + 2^L * L).

Space Complexity

  • The space complexity for the UnionFind data structure is O(N) due to storing parents for each node and their respective sizes.
  • Additional O(N) space for storing words and the dictionary d.
  • The recursive dfs function could also go up to O(L) calls deep due to recursion stack, where L is the length of the sentence.
  • The ans list may contain up to O(2^L) sentences, thus requiring O(2^L * L) space to store them when each sentence is O(L) words long.

Therefore, the space complexity is O(N + 2^L * L) considering the depths of recursion and the potential number of sentences generated.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Recommended Readings

DSU/Union Find Fundamentals

Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements

Backtracking 1

Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫