Phrases with Synonyms

Easy

A phrase is written as an array of words. You are given two phrases first and second and a list of synonym pairs synonyms, where a pair [x, y] means the words x and y can replace each other (in either direction). The phrases are equivalent if they have the same number of words and, at every position i, the words first[i] and second[i] are either identical or form a synonym pair from the list. Synonyms do not chain: pairs [a, b] and [b, c] do not make a and c synonyms. Return true if the phrases are equivalent and false otherwise.

Example 1

first=['quick', 'brown', 'fox'], second=['fast', 'brown', 'fox'], synonyms=[['fast', 'quick']] → True

"quick" and "fast" are synonyms (a pair works both ways), and the other words match exactly.

Example 2

first=['big', 'house'], second=['huge', 'home'], synonyms=[['big', 'large'], ['large', 'huge'], ['house', 'home']] → False

"big" matches "large" and "large" matches "huge", but similarity does not chain, so "big" and "huge" are not synonyms.

Example 3

first=['hello'], second=['hello', 'there'], synonyms=[] → False

The phrases have different numbers of words, so they cannot match.

Constraints

1 ≤ first.length, second.length ≤ 10⁴
0 ≤ synonyms.length ≤ 10⁴
every word is 1 to 20 English letters (lowercase or uppercase)
synonyms[i].length == 2 and all pairs are distinct

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table String