LeetCode 734: Sentence Similarity

Problem Restatement

We are given two sentences represented as arrays of words:

sentence1
sentence2

We are also given a list of similar word pairs:

similarPairs

Each pair:

[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

Example function shape:

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

Examples

Example 1

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

Compare words by position:

The answer is:

True

Example 2

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

The words are the same.

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

True

Example 3

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:

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:

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:

(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).

Each set lookup is expected O(1).

Implementation

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:

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

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

Next we build a set:

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

This gives fast lookup for each listed similar pair.

Then we compare aligned words:

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

If the words are equal, they are automatically similar:

if a == b:
    continue

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

if (a, b) in pairs:
    continue

if (b, a) in pairs:
    continue

If neither direction exists, the sentence pair fails:

return False

If every position passes, the sentences are similar:

return True

Testing

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()