> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Synonymous Sentences Python Solution

> Tested Python solution for LeetCode 1258 with 20 pytest cases. Generate a practice environment with lcpy.

LeetCode 1258, [Medium](/catalog/medium). Topics: Sort, [Union Find](/catalog/topics/union-find), [Array](/catalog/topics/array), [Hash Table](/catalog/topics/hash-table), [String](/catalog/topics/string), [Backtracking](/catalog/topics/backtracking). [View on LeetCode](https://leetcode.com/problems/synonymous-sentences/description/).

Generate this problem as a practice environment: tested reference solution, 20 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1258   # by problem number
lcpy gen -s synonymous_sentences   # by problem name
```

## Problem

You are given a list of equivalent string pairs `synonyms` where `synonyms[i] = [s<sub>i</sub>, t<sub>i</sub>]` indicates that `s<sub>i</sub>` and `t<sub>i</sub>` are equivalent strings. You are also given a sentence `text`.

Return all possible synonymous sentences **sorted lexicographically**.

### Examples

```
Input: synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]], text = "I am happy today but was sad yesterday"
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"]
Explanation: From the synonyms, happy, joy and cheerful are equivalent, and sad and sorrow are equivalent. Replacing each synonymous word independently gives 2 * 3 = 6 sentences.
```

```
Input: synonyms = [["happy","joy"],["cheerful","glad"]], 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"]
```

### Constraints

* `0 <= synonyms.length <= 10`
* `synonyms[i].length == 2`
* `1 <= s<sub>i</sub>.length, t<sub>i</sub>.length <= 10`
* `s<sub>i</sub> != t<sub>i</sub>`
* `text` consists of at most `10` words.
* All the pairs of `synonyms` are **unique**.
* The words of `text` are separated by single spaces.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/synonymous_sentences/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/synonymous_sentences/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class UnionFind:
    def __init__(self, n: int):
        self.parent: list[int] = list(range(n))
        self.size: list[int] = [1] * n

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a: int, b: int) -> None:
        root_a, root_b = self.find(a), self.find(b)
        if root_a == root_b:
            return
        if self.size[root_a] < self.size[root_b]:
            root_a, root_b = root_b, root_a
        self.parent[root_b] = root_a
        self.size[root_a] += self.size[root_b]


class Solution:
    # Time: O((s + w) * n)
    # Space: O(s + w)
    def generate_sentences(self, synonyms: list[list[str]], text: str) -> list[str]:
        words = sorted({word for pair in synonyms for word in pair})
        index = {word: i for i, word in enumerate(words)}
        uf = UnionFind(len(words))
        for first, second in synonyms:
            uf.union(index[first], index[second])

        groups: dict[int, list[str]] = {}
        for word in words:
            groups.setdefault(uf.find(index[word]), []).append(word)

        sentence = text.split()
        result: list[str] = []
        current: list[str] = []

        def dfs(i: int) -> None:
            if i == len(sentence):
                result.append(" ".join(current))
                return
            word = sentence[i]
            if word in index:
                for alt in groups[uf.find(index[word])]:
                    current.append(alt)
                    dfs(i + 1)
                    current.pop()
            else:
                current.append(word)
                dfs(i + 1)
                current.pop()

        dfs(0)
        return sorted(result)
```

## Complexity

| Time | Space |
| - | - |
| O((s + w) \* n) | O(s + w) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.