Sentence Similarity II

Sentence Similarity II is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Union-Find (Disjoint Set Union - DSU) subpattern.

Problem statement

You are given two string arrays sentence1 and sentence2, each of length n, and an array of pairs similarPairs where each similarPairs[i] = [xi, yi] indicates that the words xi and yi are similar.

A word a is considered similar to word b if: - a and b are the same word, or - a and b are directly similar (i.e., [a, b] or [b, a] is in similarPairs), or - a and b are transitively similar (i.e., there exists a sequence of words connecting a to b through direct similarities).

Note that similarity is symmetric and transitive.

Return true if sentence1 and sentence2 are similar (i.e., for every index i, sentence1[i] is similar to sentence2[i]); otherwise, return false.

Constraints: - 1 <= sentence1.length, sentence2.length <= 1000 - 1 <= sentence1[i].length, sentence2[i].length <= 20 - 0 <= similarPairs.length <= 2000 - similarPairs[i].length == 2 - All words consist of lowercase English letters only.

Topics and companies

Topics: Array, Hash Table, String, Depth-First Search, Breadth-First Search, Union Find.

Reported in interviews at Amazon.

How to practise Sentence Similarity II on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(N + M), where N is the total number of words in both sentences and M is the number of pairs. Each union/find operation is nearly O(1) due to path compression. time and O(N + M), for the mapping from words to ids and the parent array in Union-Find. space.

Open Sentence Similarity II in the code editor, or read the Sentence Similarity II editorial for a worked solution with its approach and complexity analysis.

Where Sentence Similarity II sits in the DSA pattern sheet

• Graph Traversal Patterns (DFS & BFS) pattern guide
• Union-Find (Disjoint Set Union - DSU) subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Sentence Similarity II

Other problems that use the same Union-Find (Disjoint Set Union - DSU) and Graph Traversal Patterns (DFS & BFS) techniques:

• Accounts Merge — Medium, same subpattern
• Graph Valid Tree — Medium, same subpattern
• Largest Component Size by Common Factor — Hard, same subpattern
• Most Stones Removed with Same Row or Column — Medium, same subpattern
• Number of Connected Components in an Undirected Graph — Medium, same subpattern
• Number of Islands II — Hard, same subpattern