cswork / libraryOpen practice workspace

Coding questions · Read.Ai

Compare Sentences Using Transitive Synonym Groups

Compare two tokenized sentences using undirected, transitive synonym relationships. Sentence lengths and word positions must match, while a union-find or graph traversal groups chained synonyms and leaves unknown words equivalent only to themselves.

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

Hint: Build components

Treat words as vertices and synonym pairs as undirected connections.

Hint: Compare aligned tokens

After grouping synonyms, sentence equivalence is a position-by-position check.

Compare Sentences Using Transitive Synonym Groups

Hints

  1. Build connected components from synonym pairs.
  2. After grouping words, compare the two token lists position by position.

Approach

Treat each word in a synonym pair as a vertex and union the two endpoints with a disjoint-set structure. Path compression and union by size make every connected synonym component share one representative, including transitive chains. If sentence lengths differ, return false. Otherwise compare aligned tokens: identical strings always pass; different strings pass only if both occur in the structure and have the same representative. This also keeps absent words equivalent only to themselves.

  • Time complexity: O((p + s) alpha(w)) for p pairs, s sentence positions, and w distinct paired words.
  • Space complexity: O(w) for the disjoint-set maps.