LeetCode 1258 - Synonymous Sentences

This problem asks us to generate all possible synonymous variations of a given sentence based on a list of equivalent wo

leetcodemediumarrayhash-tablestringbacktrackingsortunion-find

LeetCode Problem 1258

Difficulty: 🟡 Medium
Topics: Array, Hash Table, String, Backtracking, Sort, Union-Find

Solution

Problem Understanding

This problem asks us to generate all possible synonymous variations of a given sentence based on a list of equivalent word pairs. Each synonym pair indicates that the two words can replace each other interchangeably. The output must include all possible sentences created by substituting words with their synonyms and must be sorted lexicographically.

The inputs are:

  • synonyms: a list of word pairs, where each pair [si, ti] indicates si and ti are interchangeable. The constraints guarantee all pairs are unique and that the number of pairs is at most 10.
  • text: a sentence with up to 10 words separated by single spaces. Each word may or may not have synonyms.

The output is a list of strings, representing all valid sentences after substituting words with their synonyms, sorted lexicographically.

Key constraints and observations:

  • Because synonyms.length <= 10 and text has at most 10 words, the total number of possible sentences is relatively small and manageable for backtracking.
  • Synonym relationships can be transitive. For example, if "happy" = "joy" and "joy" = "cheerful", then "happy" = "cheerful".
  • Words without synonyms remain unchanged.
  • We must avoid duplicates and return sentences in lexicographic order.

Important edge cases:

  • No synonyms: the sentence remains unchanged.
  • Words in the sentence do not appear in synonyms.
  • Synonym pairs form a chain longer than two words.

Approaches

A brute-force approach would be to check each word in the sentence and generate all possible substitutions directly based on the provided pairs. For each word, we could recursively try every pair match. While this would produce correct sentences, it fails to account for transitive synonyms and could create duplicate results that need deduplication. Additionally, as synonyms grow, the number of combinations can explode, leading to unnecessary repeated computation.

The optimal approach leverages the Union-Find (Disjoint Set Union) data structure to group all synonyms that are transitively connected. After forming synonym groups, we can precompute a mapping from each word to its complete set of synonyms. Then, using backtracking, we iterate over each word in the sentence, substituting it with every synonym in its group and generating all possible sentences. Finally, we sort the results lexicographically.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n * m) O(2^n * m) Recursively replace words using pairs; duplicates need removal
Optimal O(n * 2^k * log(2^k)) O(n + k) Use Union-Find to group synonyms, then backtrack; sort results

Here, n is the number of words in the sentence, and k is the number of words with synonyms.

Algorithm Walkthrough

  1. Initialize a Union-Find data structure. Each unique word from the synonyms list is a node.
  2. For each synonym pair [si, ti], union the two words in the Union-Find structure, ensuring that all transitively connected synonyms share the same representative.
  3. Build a mapping from the representative of each synonym group to the sorted list of words in that group. This allows quick lookup of all synonyms for any word.
  4. Split the input text into words.
  5. Use backtracking to generate sentences. For each word in the sentence:

a. If it has synonyms in the mapping, iterate over each synonym, recursively generating sentences with that substitution.

b. If it has no synonyms, keep it unchanged and continue. 6. Collect all generated sentences into a list. 7. Sort the list lexicographically. 8. Return the sorted list.

Why it works: By using Union-Find, we correctly group all transitively connected synonyms. Backtracking ensures we explore every combination of synonymous replacements while preserving the original word order. Sorting at the end guarantees the lexicographical requirement.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def generateSentences(self, synonyms: List[List[str]], text: str) -> List[str]:
        parent = {}
        
        def find(word: str) -> str:
            if word not in parent:
                parent[word] = word
            if parent[word] != word:
                parent[word] = find(parent[word])
            return parent[word]
        
        def union(a: str, b: str):
            pa, pb = find(a), find(b)
            if pa != pb:
                parent[pa] = pb
        
        # Build union-find structure
        for a, b in synonyms:
            union(a, b)
        
        # Build mapping from root to all synonyms
        groups = defaultdict(list)
        for word in parent:
            root = find(word)
            groups[root].append(word)
        
        for key in groups:
            groups[key].sort()
        
        words = text.split()
        res = []
        
        def backtrack(index: int, path: List[str]):
            if index == len(words):
                res.append(' '.join(path))
                return
            word = words[index]
            if word in parent:
                for syn in groups[find(word)]:
                    backtrack(index + 1, path + [syn])
            else:
                backtrack(index + 1, path + [word])
        
        backtrack(0, [])
        return sorted(res)

The Python implementation first constructs the Union-Find structure and groups synonyms. Each word in the sentence is then replaced recursively by all synonyms from its group. Words without synonyms remain unchanged. Sorting ensures lexicographical order.

Go Solution

package main

import (
	"sort"
	"strings"
)

func generateSentences(synonyms [][]string, text string) []string {
	parent := map[string]string{}
	
	var find func(string) string
	find = func(word string) string {
		if _, exists := parent[word]; !exists {
			parent[word] = word
		}
		if parent[word] != word {
			parent[word] = find(parent[word])
		}
		return parent[word]
	}
	
	union := func(a, b string) {
		pa, pb := find(a), find(b)
		if pa != pb {
			parent[pa] = pb
		}
	}
	
	for _, pair := range synonyms {
		union(pair[0], pair[1])
	}
	
	groups := map[string][]string{}
	for word := range parent {
		root := find(word)
		groups[root] = append(groups[root], word)
	}
	
	for key := range groups {
		sort.Strings(groups[key])
	}
	
	words := strings.Split(text, " ")
	var res []string
	
	var backtrack func(int, []string)
	backtrack = func(index int, path []string) {
		if index == len(words) {
			res = append(res, strings.Join(path, " "))
			return
		}
		word := words[index]
		if _, exists := parent[word]; exists {
			for _, syn := range groups[find(word)] {
				backtrack(index+1, append(append([]string{}, path...), syn))
			}
		} else {
			backtrack(index+1, append(path, word))
		}
	}
	
	backtrack(0, []string{})
	sort.Strings(res)
	return res
}

The Go implementation mirrors Python but manages slices carefully to avoid modifying shared state during recursion. Maps handle Union-Find parents and groups. Lexicographic sorting is handled using sort.Strings.

Worked Examples

Example 1:

synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]]
text = "I am happy today but was sad yesterday"

Step by step:

  1. Union-Find groups: "happy", "joy", "cheerful" are connected; "sad" and "sorrow" are connected.
  2. Groups mapping:
  • root "happy": ["cheerful", "happy", "joy"]
  • root "sad": ["sad", "sorrow"]
  1. Split sentence: ["I", "am", "happy", "today", "but", "was", "sad", "yesterday"]
  2. Backtracking:
  • For "happy": try ["cheerful", "happy", "joy"]
  • For "sad": try ["sad", "sorrow"]
  1. Combine all possibilities: 3 * 2 = 6 sentences
  2. Sort lexicographically

Final output:

["I am cheerful today but was sad yesterday",
 "I am cheerful today but was sorrow yesterday",
 "I am happy today but was sad yesterday",
 "I am happy today but was sorrow yesterday",
 "I am joy today but was sad yesterday",
 "I am joy today but was sorrow yesterday"]

Example 2 works similarly but has fewer synonyms and only two resulting sentences.

Complexity Analysis

Measure Complexity Explanation
Time O(n * 2^k * log(2^k)) Backtracking explores all combinations of words with synonyms; sorting adds log factor
Space O(n + k) Union-Find parent mapping and recursion stack for backtracking

Here, n is the number of words in the sentence, k is the number of words with synonyms.

Test Cases

# Provided examples
assert Solution().generateSentences([["happy","joy"],["sad","sorrow"],["joy","cheerful"]], "I am happy today but was sad yesterday") == [
    "I am cheerful today but was sad yesterday",
    "I am cheerful today but