# LeetCode 734: Sentence Similarity

## Problem Restatement

We are given two sentences represented as arrays of words:

```python
sentence1
sentence2
```

We are also given a list of similar word pairs:

```python
similarPairs
```

Each pair:

```python
[x, y]
```

means word `x` is similar to word `y`.

Two sentences are similar if:

1. They have the same number of words.
2. Every word at index `i` in `sentence1` is similar to the word at index `i` in `sentence2`.

A word is always similar to itself.

Similarity is symmetric. If `x` is similar to `y`, then `y` is similar to `x`.

Similarity is not transitive. If `a` is similar to `b`, and `b` is similar to `c`, we cannot assume `a` is similar to `c`. This detail is explicit in the problem statement.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `sentence1`, `sentence2`, and `similarPairs` |
| Output | `True` if the sentences are similar, otherwise `False` |
| Same word | Always considered similar |
| Pair direction | Similarity works in both directions |
| Transitivity | Not allowed |

Example function shape:

```python
def areSentencesSimilar(
    sentence1: list[str],
    sentence2: list[str],
    similarPairs: list[list[str]],
) -> bool:
    ...
```

## Examples

### Example 1

```python
sentence1 = ["great", "acting", "skills"]
sentence2 = ["fine", "drama", "talent"]
similarPairs = [
    ["great", "fine"],
    ["drama", "acting"],
    ["skills", "talent"],
]
```

Compare words by position:

| Index | Word 1 | Word 2 | Similar? |
|---:|---|---|---|
| 0 | `"great"` | `"fine"` | Yes |
| 1 | `"acting"` | `"drama"` | Yes |
| 2 | `"skills"` | `"talent"` | Yes |

The answer is:

```python
True
```

### Example 2

```python
sentence1 = ["great"]
sentence2 = ["great"]
similarPairs = []
```

The words are the same.

A word is always similar to itself, so the answer is:

```python
True
```

### Example 3

```python
sentence1 = ["great"]
sentence2 = ["good"]
similarPairs = [
    ["great", "fine"],
    ["fine", "good"],
]
```

Even though `"great"` connects to `"good"` through `"fine"`, similarity is not transitive.

So `"great"` and `"good"` are not directly similar.

The answer is:

```python
False
```

## First Thought: Compare Word by Word

Sentence similarity is positional.

We do not need to compare every word in one sentence with every word in the other sentence.

We only compare:

```python
sentence1[i]
sentence2[i]
```

If the lengths are different, the sentences cannot be similar.

If the lengths are equal, each aligned pair must satisfy one of these:

1. The two words are identical.
2. The two words appear as a similar pair.

The main task is making pair lookup fast.

## Key Insight

Use a hash set.

Store each similar pair as a tuple:

```python
(x, y)
```

Then we can test whether two words are similar in expected `O(1)` time.

Since similarity is symmetric, we can either:

1. Store both directions: `(x, y)` and `(y, x)`.
2. Store the given direction only, then check both directions during lookup.

The second version is slightly smaller, and it is enough.

## Algorithm

1. If `len(sentence1) != len(sentence2)`, return `False`.
2. Convert `similarPairs` into a set of tuples.
3. For each aligned word pair `(a, b)`:
   - If `a == b`, continue.
   - If `(a, b)` is in the set, continue.
   - If `(b, a)` is in the set, continue.
   - Otherwise, return `False`.
4. Return `True`.

## Correctness

If the two sentences have different lengths, they cannot be similar by definition, so returning `False` is correct.

For equal-length sentences, the algorithm checks every aligned word pair. If the words are identical, they are similar because a word is always similar to itself. If they are not identical, the algorithm checks whether the pair appears in `similarPairs` in either direction. This correctly handles symmetric similarity.

If neither direction appears, the aligned words are not similar, so the whole sentence pair cannot be similar. Returning `False` is correct.

If the loop completes, every aligned word pair is either identical or explicitly similar. Therefore the two sentences satisfy the definition of sentence similarity, and returning `True` is correct.

The algorithm does not infer transitive similarity. It only checks direct listed pairs. This matches the problem rule that similarity is not transitive.

## Complexity

Let `n = len(sentence1)` and `p = len(similarPairs)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n + p)` | Build the set once, then scan aligned words once |
| Space | `O(p)` | Store the similar pairs in a set |

Each set lookup is expected `O(1)`.

## Implementation

```python
class Solution:
    def areSentencesSimilar(
        self,
        sentence1: list[str],
        sentence2: list[str],
        similarPairs: list[list[str]],
    ) -> bool:
        if len(sentence1) != len(sentence2):
            return False

        pairs = {(a, b) for a, b in similarPairs}

        for a, b in zip(sentence1, sentence2):
            if a == b:
                continue

            if (a, b) in pairs:
                continue

            if (b, a) in pairs:
                continue

            return False

        return True
```

## Code Explanation

First we check sentence length:

```python
if len(sentence1) != len(sentence2):
    return False
```

Two sentences with different word counts cannot match position by position.

Next we build a set:

```python
pairs = {(a, b) for a, b in similarPairs}
```

This gives fast lookup for each listed similar pair.

Then we compare aligned words:

```python
for a, b in zip(sentence1, sentence2):
```

If the words are equal, they are automatically similar:

```python
if a == b:
    continue
```

If the words are different, we check both pair directions:

```python
if (a, b) in pairs:
    continue

if (b, a) in pairs:
    continue
```

If neither direction exists, the sentence pair fails:

```python
return False
```

If every position passes, the sentences are similar:

```python
return True
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.areSentencesSimilar(
        ["great", "acting", "skills"],
        ["fine", "drama", "talent"],
        [["great", "fine"], ["drama", "acting"], ["skills", "talent"]],
    ) is True

    assert s.areSentencesSimilar(
        ["great"],
        ["great"],
        [],
    ) is True

    assert s.areSentencesSimilar(
        ["great"],
        ["good"],
        [["great", "fine"], ["fine", "good"]],
    ) is False

    assert s.areSentencesSimilar(
        ["great", "acting"],
        ["fine"],
        [["great", "fine"]],
    ) is False

    assert s.areSentencesSimilar(
        ["fine", "drama"],
        ["great", "acting"],
        [["great", "fine"], ["acting", "drama"]],
    ) is True

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Three matching similar pairs | Basic valid case |
| Same word with no pairs | Self-similarity |
| Transitive-looking chain | Confirms no transitive inference |
| Different lengths | Must fail immediately |
| Reversed pair direction | Confirms symmetry |