737. Sentence Similarity II

Sentence Similarity II (LeetCode 737) 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.

How to solve Sentence Similarity II

Sentence Similarity II is a Union-Find problem, part of Graph Traversal Patterns (DFS & BFS). Master Union-Find data structure with path compression and union by rank for connectivity problems.

Work towards the solution in these steps:

1. Consider the graphs where each pair in "pairs" is an edge. Two words are similar if they are the same, or are in the same connected component of this graph.

The reference solution runs in O(N + M) time and O(N + M) space.

The Sentence Similarity II solution and editorial walks through the full approach with reference code.

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.

Examples

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) time and O(N + M) 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

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
• Greatest Common Divisor Traversal — Hard, 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

Sentence Similarity II FAQ