Given two arrays of strings sentence1 and sentence2, and an array of string pairs similarPairs where each similarPairs[i] = [x_i, y_i] indicates that the words x_i and y_i are similar, determine if sentence1 and sentence2 are similar.

Two sentences are similar if:

• They have the same length.

• For each valid index i, the word sentence1[i] is similar to sentence2[i].

Similarity is an equivalence relation:

• Every word is similar to itself.

• If word $A$ is similar to word $B$, then word $B$ is similar to word $A$.

• If word $A$ is similar to word $B$ and word $B$ is similar to word $C$, then word $A$ is similar to word $C$.

Return true if sentence1 and sentence2 are similar, and false otherwise.

Note: Similarity relation is transitive, unlike Sentence Similarity I.

Constraints:

• $1 \leq$ sentence1.length, sentence2.length $\leq 1000$

• $1 \leq$ sentence1[i].length, sentence2[i].length $\leq 20$

• sentence1[i] and sentence2[i] consist of lowercase and uppercase English letters.

• $0 \leq$ similarPairs.length $\leq 2000$

• similarPairs[i].length $= 2$

• $1 \leq$ x_i.length, y_i.length $\leq 20$

• x_i and y_i consist of English letters.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.