Sentence Similarity II - Practice Coding Problems

Sentence Similarity II - Problem

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

Sentence Similarity with Transitive Relations

Given two sentences represented as string arrays and a list of word similarity pairs, determine if the sentences are similar.

Two sentences are considered similar if:
• They have the same length (same number of words)
• Each word at position i in sentence1 is similar to the word at position i in sentence2

The key challenge is that similarity is transitive: if word A is similar to word B, and word B is similar to word C, then A and C are also similar. Every word is always similar to itself.

Example: If we have pairs [("great", "fine"), ("fine", "good")], then "great" and "good" are similar through the transitive relationship.

Your task is to efficiently determine if two sentences can be considered similar given these transitive similarity relationships.

Input & Output

example_1.py — Basic Similarity

$ Input: sentence1 = ["great", "acting", "skills"] sentence2 = ["fine", "drama", "talent"] similarPairs = [["great","fine"],["drama","acting"],["skills","talent"]]

› Output: true

💡 Note: Each word at corresponding positions are directly similar: 'great'↔'fine', 'acting'↔'drama', 'skills'↔'talent'. Since all positions match through direct similarity pairs, the sentences are similar.

example_2.py — Transitive Similarity

$ Input: sentence1 = ["great", "acting"] sentence2 = ["good", "drama"] similarPairs = [["great","fine"],["fine","good"],["acting","drama"]]

› Output: true

💡 Note: Position 0: 'great' and 'good' are similar through transitive relationship: great→fine→good. Position 1: 'acting' and 'drama' are directly similar. Both positions satisfy similarity requirements.

example_3.py — Different Lengths

$ Input: sentence1 = ["I", "love", "coding"] sentence2 = ["I", "love"] similarPairs = []

› Output: false

💡 Note: The sentences have different lengths (3 vs 2 words), so they cannot be similar regardless of similarity pairs. This is caught immediately without processing any pairs.

Constraints

1 ≤ sentence1.length, sentence2.length ≤ 1000
1 ≤ sentence1[i].length, sentence2[i].length ≤ 20
sentence1[i] and sentence2[i] consist of lowercase English letters
0 ≤ similarPairs.length ≤ 2000
similarPairs[i].length == 2
1 ≤ similarPairs[i][0].length, similarPairs[i][1].length ≤ 20
similarPairs[i][0] and similarPairs[i][1] consist of lowercase English letters
Key insight: Similarity relation is transitive and reflexive

Visualization

Tap to expand

Understanding the Visualization

Build Social Circles

Start with everyone as individual nodes, then merge friends into communities

Process Friendships

For each friendship pair, union their communities using efficient path compression

Query Relationships

To check if two people are connected, verify they belong to the same community

Key Takeaway

🎯 Key Insight: Union-Find transforms the complex problem of checking transitive relationships into simple community membership queries, achieving near-constant time complexity for each comparison.

Asked in

G Google 42 f Facebook 38 a Amazon 31 ⊞ Microsoft 25

The optimal solution uses Union-Find (Disjoint Set Union) to efficiently handle transitive similarity relationships. First, we build connected components by unioning all similar word pairs. Then, for each sentence position, we check if the corresponding words belong to the same component in O(α(n)) time. This approach excels when dealing with multiple similarity queries as it preprocesses the transitive closure once and answers queries nearly instantly.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force DFS for Each Pair	O(n × (V + E))	O(V + E)	For each word pair, run DFS to check if they're connected through similarity chains
Union-Find (Optimal)	O(P × α(W) + N × α(W))	O(W)	Use Union-Find to group similar words, then check if word pairs belong to same component

Brute Force DFS for Each Pair — Algorithm Steps

Check if sentences have equal length
Build adjacency list from similarity pairs
For each position i, run DFS from sentence1[i] to find sentence2[i]
If any position fails, return false

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Graph

Create adjacency list from similarity pairs

Compare Position 0

Run DFS to check if words at position 0 are connected

Repeat for All

Continue DFS search for each remaining position

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_WORDS 1000
#define MAX_WORD_LEN 20

typedef struct {
    char words[MAX_WORDS][MAX_WORD_LEN];
    int count;
} WordList;

typedef struct {
    WordList adj[MAX_WORDS];
    char vertices[MAX_WORDS][MAX_WORD_LEN];
    int vertex_count;
} Graph;

int find_vertex(Graph* graph, const char* word) {
    for (int i = 0; i < graph->vertex_count; i++) {
        if (strcmp(graph->vertices[i], word) == 0) {
            return i;
        }
    }
    strcpy(graph->vertices[graph->vertex_count], word);
    graph->adj[graph->vertex_count].count = 0;
    return graph->vertex_count++;
}

bool dfs(Graph* graph, int start, int target, bool visited[]) {
    if (start == target) return true;
    visited[start] = true;
    
    for (int i = 0; i < graph->adj[start].count; i++) {
        int neighbor = find_vertex(graph, graph->adj[start].words[i]);
        if (!visited[neighbor]) {
            if (dfs(graph, neighbor, target, visited)) {
                return true;
            }
        }
    }
    return false;
}

bool areSentencesSimilarTwo(char** sentence1, int sentence1Size, char** sentence2, int sentence2Size, char*** similarPairs, int similarPairsSize) {
    if (sentence1Size != sentence2Size) {
        return false;
    }
    
    Graph graph = {0};
    
    // Build adjacency list
    for (int i = 0; i < similarPairsSize; i++) {
        int v1 = find_vertex(&graph, similarPairs[i][0]);
        int v2 = find_vertex(&graph, similarPairs[i][1]);
        
        strcpy(graph.adj[v1].words[graph.adj[v1].count++], similarPairs[i][1]);
        strcpy(graph.adj[v2].words[graph.adj[v2].count++], similarPairs[i][0]);
    }
    
    // Check each position
    for (int i = 0; i < sentence1Size; i++) {
        if (strcmp(sentence1[i], sentence2[i]) != 0) {
            bool visited[MAX_WORDS] = {false};
            int start = find_vertex(&graph, sentence1[i]);
            int target = find_vertex(&graph, sentence2[i]);
            
            if (!dfs(&graph, start, target, visited)) {
                return false;
            }
        }
    }
    
    return true;
}

int main() {
    // Parse input and call solution
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × (V + E))

n word comparisons, each requiring DFS through V vertices and E edges

✓ Linear Growth

Space Complexity

O(V + E)

Space for adjacency list and DFS recursion stack

✓ Linear Space

28.6K Views

Medium-High Frequency

~22 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force DFS for Each Pair — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler