Compare Sentences Using Transitive Synonym Groups

Problem

Given synonym pairs and two tokenized sentences, return whether the sentences are equivalent. They are equivalent only if they have the same number of words and every pair of words at the same position is either identical or connected through one or more synonym pairs. Synonymy is undirected and transitive.

Constraints & Assumptions

• There are at most 100,000 synonym pairs.
• Each sentence contains at most 100,000 lowercase words.
• A word may appear in several pairs and form a larger synonym group.
• Words absent from all pairs are equivalent only to themselves.

Clarifications

• Sentence word order cannot change.
• Synonym pairs are symmetric even if listed once.
• Transitive chains such as hit -> hits -> hitted belong to one group.

Examples

pairs = [["flat", "flatting"], ["hit", "hits"], ["hits", "hitted"]]
a = ["flat", "the", "word"]
b = ["flatting", "the", "word"]
output = true

a = ["hit", "the", "click"]
b = ["hitted", "one", "click"]
output = false

Hints