Chains of Synonyms

Medium

Two phrases are given as word lists first and second. There is also a synonym dictionary synonyms: each pair [x, y] says that x and y are synonyms. Being synonyms works both ways and carries along a chain: if a is a synonym of b and b is a synonym of c, then a and c are synonyms too. Every word is a synonym of itself. The phrases **mean the same** when they have the same number of words and, for every position i, the words first[i] and second[i] are synonyms. Return True if so, otherwise False.

Example 1

first=["a", "quick", "trip"], second=["a", "rapid", "journey"], synonyms=[["quick", "fast"], ["rapid", "fast"], ["trip", "journey"]] → True

"a" matches itself, quick → fast → rapid are linked by a chain, and trip and journey are direct synonyms.

Example 2

first=["big", "house"], second=["large", "home"], synonyms=[["big", "large"], ["home", "flat"]] → False

No chain of synonyms connects house and home.

Example 3

first=["hi"], second=["hi", "there"], synonyms=[] → False

The word counts differ, so the phrases cannot match.

Constraints

1 ≤ len(first), len(second) ≤ 10⁴
0 ≤ len(synonyms) ≤ 2·10⁴, and each pair holds two words
Every word is 1 to 20 characters of English letters (upper or lower case; case matters)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search Union Find Array Hash Table String

Similar problems

Merge Contact Cards Medium Rearrange Through Links Medium One-Swap Word Families Hard Ratio Chain Queries Medium A Board Cut by Slashes Medium

Input

first=["a", "quick", "trip"], second=["a", "rapid", "journey"], synonyms=[["quick", "fast"], ["rapid", "fast"], ["trip", "journey"]]

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 111 tests on the server, hidden ones included.