Sentence Similarity III — Medium Problem & Solution

Problem statement

Two sentences are similar when one can be turned into the other by inserting a single (possibly empty) sentence at some word boundary — the start, the end, or between two words.

A sentence is a sequence of words separated by single spaces, with no leading or trailing space.

Return whether sentence1 and sentence2 are similar.

Example 1

Input: sentence1 = "CodeKairo runs a daily kata", sentence2 = "CodeKairo kata"
Output: true
Explanation: Inserting "runs a daily" after the first word of the shorter sentence gives the longer one.

Example 2

Input: sentence1 = "of", sentence2 = "A lot of words"
Output: false
Explanation: "of" sits in the middle, so it is neither a prefix nor a suffix.

Example 3

Input: sentence1 = "Solving right now", sentence2 = "Solving"
Output: true
Explanation: The shorter sentence is a prefix of the longer one.

Constraints

• 1 <= sentence length <= 100
• Words contain only English letters.
• Words are separated by single spaces with no leading or trailing space.

How to solve Sentence Similarity III

Inserting one contiguous block means the shorter word list appears in the longer one as a prefix followed by a suffix, with the insertion in between. Greedily matching as far as possible from each end settles it.

Approach

1. Split both sentences on spaces and call the shorter list a, the longer b.
2. Advance i while a[i] equals b[i].
3. Advance j while a[|a|-1-j] equals b[|b|-1-j], stopping before the two runs overlap.
4. They are similar exactly when i + j >= |a|.

Why it works

The prefix and suffix matches are independent and each is maximal, so if any split of a into a prefix and a suffix works, the greedy runs are at least as long. Capping j at |a| - i stops the same word being counted twice, which would wrongly accept a short sentence made of repeated words.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• Character-level prefix/suffix matching accepts "CodeKairo" against "CodeKairos rank", which is wrong — the insertion must land on a word boundary.
• Forgetting the j < |a| - i cap double-counts words when the sentences share repeats.
• Equal sentences are similar: the inserted sentence may be empty.

Reference solution

Python

def areSentencesSimilar(sentence1: str, sentence2: str) -> bool:
    a = sentence1.split(" ")
    b = sentence2.split(" ")
    if len(a) > len(b):
        a, b = b, a
    i = 0
    while i < len(a) and a[i] == b[i]:
        i += 1
    j = 0
    while j < len(a) - i and a[len(a) - 1 - j] == b[len(b) - 1 - j]:
        j += 1
    return i + j >= len(a)

JavaScript

var areSentencesSimilar = function(sentence1, sentence2) {
    var a = sentence1.split(" ");
    var b = sentence2.split(" ");
    if (a.length > b.length) { var t = a; a = b; b = t; }
    var i = 0;
    while (i < a.length && a[i] === b[i]) i++;
    var j = 0;
    while (j < a.length - i && a[a.length - 1 - j] === b[b.length - 1 - j]) j++;
    return i + j >= a.length;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Make Three Strings Equal Medium
• Number of Ways to Divide a Long Corridor Medium
• Maximum Number of Non-overlapping Palindrome Substrings Medium
• Count Number of Texts Medium
• Delete Characters to Make Fancy String Medium
• Count Number of Homogenous Substrings Medium