Sentence Similarity - Practice Coding Problems

Sentence Similarity - Problem

We can represent a sentence as an array of words. For example, the sentence "I am happy with leetcode" can be represented as arr = ["I","am","happy","with","leetcode"].

Given two sentences sentence1 and sentence2 each represented as a string array and given an array of string pairs similarPairs where similarPairs[i] = [xi, yi] indicates that the two words xi and yi are similar.

Return true if sentence1 and sentence2 are similar, or false if they are not similar.

Two sentences are similar if:

They have the same length (i.e., the same number of words)
sentence1[i] and sentence2[i] are similar for all i

Note: A word is always similar to itself. The similarity relation is not transitive. For example, if words a and b are similar, and words b and c are similar, a and c are not necessarily similar.

Input & Output

Example 1 — Basic Similarity

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

› Output: true

💡 Note: Both sentences have length 2. Position 0: "great" and "fine" are both similar to "good" but not directly similar. Position 1: "acting" and "drama" are directly similar via the pair ["acting","drama"].

Example 2 — Direct Similarity

$ Input: sentence1 = ["great"], sentence2 = ["great"], similarPairs = []

› Output: true

💡 Note: Single word sentences. "great" is identical to "great", so they are similar even with no similarity pairs.

Example 3 — No Similarity

$ Input: sentence1 = ["great"], sentence2 = ["doubleplus"], similarPairs = [["great","good"]]

› Output: false

💡 Note: "great" and "doubleplus" are not identical and there's no similarity pair connecting them directly.

Constraints

1 ≤ sentence1.length, sentence2.length ≤ 1000
1 ≤ sentence1[i].length, sentence2[i].length ≤ 20
0 ≤ similarPairs.length ≤ 1000
similarPairs[i].length == 2

Visualization

Tap to expand

Understanding the Visualization

Input

Two sentences and similarity pairs

Process

Check length equality and word-by-word similarity

Output

Boolean result indicating similarity

Key Takeaway

🎯 Key Insight: Use hash set to store all similarity pairs (bidirectional) for O(1) lookup when checking word similarity

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to efficiently check word similarity using a hash set. The optimal approach builds a hash set of all similarity pairs (bidirectional) for O(1) lookup, then compares each word position. Time: O(m + n), Space: O(m).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Set Optimization	O(m + n)	O(m)	Build a hash set of similarity pairs for O(1) lookup time
Brute Force Linear Search	O(n × m)	O(1)	For each word pair, scan through all similarity pairs to check if they match

Hash Set Optimization — Algorithm Steps

Build hash set with all similarity pairs in both directions
Check if sentences have same length
For each position, check if words are identical or exist in similarity set

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Hash Set

Store all similarity pairs (both directions) in hash set

Quick Lookup

Check each word pair against hash set in O(1) time

Result

Return true if all pairs found

Code -

solution.c — C

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

#define MAX_PAIRS 10000
struct HashEntry {
    char key[205];
    bool exists;
};

struct HashEntry hashTable[MAX_PAIRS];
int hashSize = 0;

unsigned int hash(char* str) {
    unsigned int hash = 5381;
    while (*str) hash = ((hash << 5) + hash) + *str++;
    return hash % MAX_PAIRS;
}

void insertHash(char* key) {
    unsigned int index = hash(key);
    while (hashTable[index].exists && strcmp(hashTable[index].key, key) != 0) {
        index = (index + 1) % MAX_PAIRS;
    }
    if (!hashTable[index].exists) {
        strcpy(hashTable[index].key, key);
        hashTable[index].exists = true;
    }
}

bool findHash(char* key) {
    unsigned int index = hash(key);
    while (hashTable[index].exists) {
        if (strcmp(hashTable[index].key, key) == 0) return true;
        index = (index + 1) % MAX_PAIRS;
    }
    return false;
}

bool solution(char sentence1[][101], int len1, char sentence2[][101], int len2, char similarPairs[][2][101], int pairsLen) {
    if (len1 != len2) {
        return false;
    }
    
    // Build hash table
    for (int i = 0; i < pairsLen; i++) {
        char key1[205], key2[205];
        sprintf(key1, "%s,%s", similarPairs[i][0], similarPairs[i][1]);
        sprintf(key2, "%s,%s", similarPairs[i][1], similarPairs[i][0]);
        insertHash(key1);
        insertHash(key2);
    }
    
    for (int i = 0; i < len1; i++) {
        if (strcmp(sentence1[i], sentence2[i]) == 0) {
            continue;
        }
        
        char key[205];
        sprintf(key, "%s,%s", sentence1[i], sentence2[i]);
        if (!findHash(key)) {
            return false;
        }
    }
    
    return true;
}

int main() {
    char sentence1[100][101], sentence2[100][101];
    char similarPairs[1000][2][101];
    int len1 = 0, len2 = 0, pairsLen = 0;
    
    char line[10000];
    fgets(line, sizeof(line), stdin);
    // Parse sentence1
    
    fgets(line, sizeof(line), stdin);
    // Parse sentence2
    
    fgets(line, sizeof(line), stdin);
    // Parse similarPairs
    
    bool result = solution(sentence1, len1, sentence2, len2, similarPairs, pairsLen);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m + n)

O(m) to build hash set from m pairs, O(n) to check n word positions

✓ Linear Growth

Space Complexity

O(m)

Hash set stores up to 2m entries (both directions of m pairs)

✓ Linear Space

28.4K Views

Medium Frequency

~15 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

Hash Set Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler