Sentence Similarity III - Practice Coding Problems

Sentence Similarity III - Problem

You are given two strings sentence1 and sentence2, each representing a sentence composed of words. A sentence is a list of words that are separated by a single space with no leading or trailing spaces. Each word consists of only uppercase and lowercase English characters.

Two sentences s1 and s2 are considered similar if it is possible to insert an arbitrary sentence (possibly empty) inside one of these sentences such that the two sentences become equal. Note that the inserted sentence must be separated from existing words by spaces.

For example:

s1 = "Hello Jane" and s2 = "Hello my name is Jane" can be made equal by inserting "my name is" between "Hello" and "Jane" in s1.
s1 = "Frog cool" and s2 = "Frogs are cool" are not similar, since although there is a sentence "s are" inserted into s1, it is not separated from "Frog" by a space.

Given two sentences sentence1 and sentence2, return true if sentence1 and sentence2 are similar. Otherwise, return false.

Input & Output

Example 1 — Basic Insertion

$ Input: sentence1 = "Hello Jane", sentence2 = "Hello my name is Jane"

› Output: true

💡 Note: We can insert "my name is" between "Hello" and "Jane" in sentence1 to make it equal to sentence2. The prefix "Hello" matches and the suffix "Jane" matches.

Example 2 — Invalid Word Boundary

$ Input: sentence1 = "Frog cool", sentence2 = "Frogs are cool"

› Output: false

💡 Note: Although we can insert "s are" into sentence1, it would merge with "Frog" to form "Frogs", which violates the word boundary requirement.

Example 3 — Identical Sentences

$ Input: sentence1 = "Hello World", sentence2 = "Hello World"

› Output: true

💡 Note: Both sentences are identical, so we can insert an empty string (no words) to make them equal.

Constraints

1 ≤ sentence1.length, sentence2.length ≤ 100
sentence1 and sentence2 consist of lowercase and uppercase English letters and spaces
Words are separated by a single space
No leading or trailing spaces

Visualization

Tap to expand

Understanding the Visualization

Input

Two sentences with different word counts

Process

Find if insertion can make them equal

Output

Boolean result of similarity check

Key Takeaway

🎯 Key Insight: Two sentences are similar if one can be formed by inserting a contiguous block of words into the other at exactly one position

Asked in

f Facebook 15 G Google 12 a Amazon 8

The key insight is that two sentences are similar if one can be formed by inserting a contiguous sequence of words into the other. The optimal approach uses two pointers to find the longest common prefix and suffix, then checks if all words in the shorter sentence are covered. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers (Prefix/Suffix Match)	O(n)	O(n)	Find common prefix and suffix, check if middle part can be inserted
Brute Force	O(n³)	O(n)	Try all possible ways to insert substring into shorter sentence

Two Pointers (Prefix/Suffix Match) — Algorithm Steps

Split both sentences into word arrays
Find longest common prefix using left pointer
Find longest common suffix using right pointer
Check if remaining words form valid insertion

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Prefix

Match words from the beginning

Find Suffix

Match words from the end

Check Coverage

Verify all words of shorter sentence are covered

Code -

solution.c — C

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

#define MAX_LEN 1000
#define MAX_WORDS 100

int split(char* s, char words[][MAX_LEN]) {
    int count = 0;
    char* token = strtok(s, " ");
    while (token != NULL && count < MAX_WORDS) {
        strcpy(words[count], token);
        count++;
        token = strtok(NULL, " ");
    }
    return count;
}

bool solution(char* sentence1, char* sentence2) {
    char words1[MAX_WORDS][MAX_LEN], words2[MAX_WORDS][MAX_LEN];
    char s1Copy[MAX_LEN], s2Copy[MAX_LEN];
    strcpy(s1Copy, sentence1);
    strcpy(s2Copy, sentence2);
    
    int n1 = split(s1Copy, words1);
    int n2 = split(s2Copy, words2);
    
    // Ensure words1 is the shorter sentence
    if (n1 > n2) {
        char temp[MAX_WORDS][MAX_LEN];
        memcpy(temp, words1, sizeof(words1));
        memcpy(words1, words2, sizeof(words2));
        memcpy(words2, temp, sizeof(temp));
        int tempN = n1;
        n1 = n2;
        n2 = tempN;
    }
    
    // Find longest common prefix
    int i = 0;
    while (i < n1 && strcmp(words1[i], words2[i]) == 0) {
        i++;
    }
    
    // Find longest common suffix
    int j = 0;
    while (j < n1 - i && strcmp(words1[n1 - 1 - j], words2[n2 - 1 - j]) == 0) {
        j++;
    }
    
    // Check if we've matched all words of shorter sentence
    return i + j >= n1;
}

int main() {
    char sentence1[MAX_LEN], sentence2[MAX_LEN];
    fgets(sentence1, sizeof(sentence1), stdin);
    sentence1[strcspn(sentence1, "\n")] = 0;
    fgets(sentence2, sizeof(sentence2), stdin);
    sentence2[strcspn(sentence2, "\n")] = 0;
    
    bool result = solution(sentence1, sentence2);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to find prefix, single pass to find suffix, where n is total words

✓ Linear Growth

Space Complexity

O(n)

Store word arrays for both sentences

⚡ Linearithmic Space

28.5K 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

Two Pointers (Prefix/Suffix Match) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler