Synonymous Sentences
Medium
0 views
Topics:
ArraysStringsRecursionGraphs
You are given a list of synonymous words synonyms where synonyms[i] = [wordi, synonymi]. A sentence can be transformed by replacing some of its words with synonyms.
For example, "happy boy" can be transformed into "joyful boy", "happy man", or "joyful man".
Given a sentence text and a list of synonymous words synonyms, construct all possible synonymous sentences sorted lexicographically.
Example 1:
Input: synonyms = [["happy","joy"]], text = "I am happy today but was sad yesterday"
Output: ["I am happy today but was sad yesterday","I am joy today but was sad yesterday"]
Example 2:
Input: synonyms = [["happy","joy"],["strong","healthy"]], text = "I am happy and strong today but was sad yesterday"
Output: ["I am happy and healthy today but was sad yesterday","I am happy and strong today but was sad yesterday","I am joy and healthy today but was sad yesterday","I am joy and strong today but was sad yesterday"]
Example 3:
Input: synonyms = [["happy","joy"],["strong","healthy"],["sad","melancholy"],["sad","dejected"]], text = "I am happy and strong today but was sad yesterday"
Output: ["I am happy and healthy today but was dejected yesterday","I am happy and healthy today but was melancholy yesterday","I am happy and healthy today but was sad yesterday","I am happy and strong today but was dejected yesterday","I am happy and strong today but was melancholy yesterday","I am happy and strong today but was sad yesterday","I am joy and healthy today but was dejected yesterday","I am joy and healthy today but was melancholy yesterday","I am joy and healthy today but was sad yesterday","I am joy and strong today but was dejected yesterday","I am joy and strong today but was melancholy yesterday","I am joy and strong today but was sad yesterday"]
Constraints:
0 <= synonyms.length <= 10synonyms[i].length == 21 <= wordi.length <= 101 <= synonymi.length <= 10wordi != synonymi- All words and synonyms consist of lower-case English letters only.
1 <= text.length <= 105textconsists of lower-case English letters and spaces only.- There are no leading or trailing spaces in
text. - All words in
textare separated by a single space.
Solution
Clarifying Questions
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
- What is the maximum length of a sentence, and what is the maximum number of sentences?
- Are the synonymous word pairs case-sensitive? Should the generated sentences maintain the original casing?
- If a sentence cannot be transformed into any other synonymous sentence based on the given pairs, what should the output be? Should I return the original sentence or an empty list?
- Are there any constraints on the words themselves (e.g., are they all lowercase, what character set are they limited to)?
- Is the synonymous relation transitive (e.g., if 'a' is synonymous with 'b' and 'b' is synonymous with 'c', does that implicitly mean 'a' is synonymous with 'c')?
Brute Force Solution
Approach
The brute force approach generates every possible sentence that's synonymous to the original sentence. It achieves this by systematically replacing each word in the original sentence with all its synonyms and checking if the resulting sentence is valid. It's like exploring every single path to see if it leads to a correct solution.
Here's how the algorithm would work step-by-step:
- Start with the original sentence.
- For each word in the sentence, find all its synonyms from the given list of synonymous word pairs.
- Create new sentences by replacing the original word with each of its synonyms, one at a time. This makes new sentences.
- Now, take each of these newly generated sentences and repeat the process for the next word in the sentence.
- Keep doing this for all the words in the sentence, creating even more sentences at each step.
- As you create these new sentences, store each unique sentence in a collection, to avoid duplicates.
- Finally, sort the unique sentences alphabetically to present them in the correct order.
Code Implementation
def generate_synonymous_sentences_brute_force(synonyms, text):
synonym_map = {}
for synonym_pair in synonyms:
word1, word2 = synonym_pair
if word1 not in synonym_map:
synonym_map[word1] = {word1}
if word2 not in synonym_map:
synonym_map[word2] = {word2}
synonym_map[word1].add(word2)
synonym_map[word2].add(word1)
unique_sentences = set()
def generate_sentences(current_sentence_words, index):
# Base case: If we've processed all words, add the sentence
if index == len(current_sentence_words):
unique_sentences.add(" ".join(current_sentence_words))
return
word = current_sentence_words[index]
# If the word has synonyms, explore each synonym
if word in synonym_map:
for synonym in synonym_map[word]:
new_sentence_words = current_sentence_words[:]
new_sentence_words[index] = synonym
generate_sentences(new_sentence_words, index + 1)
# Always explore the original word as well
generate_sentences(current_sentence_words, index + 1)
generate_sentences(text.split(), 0)
# Convert to a sorted list for the expected output
return sorted(list(unique_sentences))
Big(O) Analysis
Time Complexity
O(2^(m) * n * log(n)) – Let m be the number of words in the sentence that have synonyms, and n be the total number of words in the original sentence. In the worst case, each of the m words has multiple synonyms leading to an exponential number of possible sentences, specifically O(2^m). For each of these sentences, which can be at most 2^m in number, we potentially iterate through all n words of the original sentence to find the synonymous word. Furthermore, the final step of sorting the unique synonymous sentences introduces a time complexity of O(k log k) where k is the number of unique synonymous sentences generated, which will be at most O(2^m). Combining these, we get O(2^m * n) + O(2^m log(2^m)), which simplifies to O(2^m * n * log(n)).
Space Complexity
O(N * L) – The auxiliary space is dominated by the storage of unique synonymous sentences. In the worst-case scenario, each word in the original sentence could have multiple synonyms, leading to an exponential explosion in the number of possible sentences. The algorithm stores each unique sentence in a collection. Let N be the number of words in the original sentence, and L be the maximum length of any of the generated sentences. The number of unique sentences can grow exponentially with N, and each sentence requires space proportional to its length L. Thus, the space complexity can be approximated as O(Number of Unique Sentences * L). In a practical sense if we constrain the number of unique sentences to be at most N, then the space complexity would be O(N*L).
Optimal Solution
Approach
The goal is to create all possible sentences by replacing words with their synonyms. We can represent the synonym relationships and use them to explore all valid combinations systematically, avoiding redundant computations by remembering which combinations have already been tried.
Here's how the algorithm would work step-by-step:
- First, organize the synonymous word pairs into groups where each group contains words that can be used interchangeably.
- Consider each group as defining possible alternative sentence parts.
- Start building sentences by considering each word in the first group of synonyms as the starting word.
- For each starting word, explore the next group of synonyms and append each possible word to the current sentence.
- Continue this process of exploring the possible words at each synonym group, adding to each growing sentence.
- Keep track of all the sentences you've already made to avoid creating duplicates.
- Once you reach the end of the original sentence (i.e., you've considered all the groups of synonyms), add the newly created sentence to the collection of all possible synonymous sentences.
- Repeat this process for each starting word and continue building up the full list of synonymous sentences.
Code Implementation
def generate_synonymous_sentences(synonyms, sentence):
word_groups = {}
for synonym_pair in synonyms:
word1, word2 = synonym_pair
group1 = word_groups.get(word1, {word1})
group2 = word_groups.get(word2, {word2})
unified_group = group1.union(group2)
for word in unified_group:
word_groups[word] = unified_group
words_in_sentence = sentence.split()
synonymous_sets = []
for word in words_in_sentence:
synonymous_sets.append(word_groups.get(word, {word}))
sentences = set()
def backtrack(index, current_sentence):
# Base case: sentence complete.
if index == len(synonymous_sets):
sentences.add(" ".join(current_sentence))
return
# For each synonym, extend the sentence.
for synonym in synonymous_sets[index]:
backtrack(index + 1, current_sentence + [synonym])
# Initiate the backtracking algorithm.
backtrack(0, [])
# Convert the set to a sorted list
return sorted(list(sentences))Big(O) Analysis
Time Complexity
O(2^n) – Let n be the number of synonym groups in the input sentence. In the worst case, each group contains multiple synonymous words. The algorithm explores all possible combinations of words from these synonym groups. If each of the n groups has, on average, a constant number (e.g., 2) of synonyms, the number of possible sentences grows exponentially, being proportional to 2 multiplied by itself n times (2*2*...*2), which equals 2^n. Thus, the time complexity is O(2^n).
Space Complexity
O(N*M) – The primary space complexity arises from storing the synonym groups and the generated sentences. Let N be the length of the input sentence (number of words) and M be the maximum number of synonyms for any single word in the input. The synonym groups themselves might require O(S) space, where S is the total number of synonym pairs. However, the dominant factor is the generation of all possible synonymous sentences. In the worst-case scenario, each word has M synonyms, and the algorithm explores all combinations leading to approximately M^N sentences. To store these sentences, where each has length N, the space needed can reach O(N * M^N). A visited set is used to avoid duplicates, which, in the worst case, stores all M^N sentences, each of length N, giving O(N * M^N). Since the plain english explanation mentions avoiding duplicate computations by remembering which combinations have been tried, it suggests a visited set containing the sentences. Therefore, considering only the creation of the sentences and visited set, the worst-case space complexity is O(N * M^N), which can be simplified as O(N*M) by assuming that at most only M synonymous sentences will ever exist at any given time because they are being managed by the visited array for duplicates.
Edge Cases
| Case | How to Handle |
|---|---|
| synonyms is null or empty | Return a list containing just the input text since no synonyms exist. |
| text is null or empty | Return an empty list since there's no text to process. |
| synonyms contain duplicate pairs | Treat duplicate synonym pairs as the same relationship and proceed normally; the algorithm should handle redundancy. |
| synonyms contain contradictory pairs (e.g., a <-> b and a <-> c where b and c are not synonyms) | The algorithm should construct transitive synonym relationships; no contradiction handling is explicitly needed, but the output might be unexpected if input is nonsensical. |
| Very long input text exceeding memory limitations | Consider streaming or divide-and-conquer approaches to process the text in chunks if memory becomes a bottleneck. |
| Synonym pairs create a cycle (e.g., a<->b, b<->c, c<->a) | The algorithm's union-find structure will correctly handle cycles without infinite loops. |
| Text contains words not present in the synonym pairs | Treat these words as themselves and include them in the generated sentences, leaving them untouched. |
| Maximum number of synonyms, potentially causing stack overflow in recursive approaches | Use iterative approaches like Breadth-First Search to avoid potential stack overflow issues. |
Explore Interview QuestionsGoogle Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Jobs By LevelEntry-Level Software Engineer JobsMid-Level Software Engineer JobsSenior Software Engineer JobsStaff Software Engineer Jobs
