Sentence Similarity III

Medium
773.

Sentence Similarity III

Sentence Similarity III is a medium coding problem on arrays, strings and two pointers, asked in Amazon, Meta and Wipro interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} sentence1
 * @param {string} sentence2
 * @return {boolean}
 */
var areSentencesSimilar = function(sentence1, sentence2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Sentence Similarity III — Solution in Python, Java & C++

Sentence Similarity III solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Sentence Similarity III is a medium coding problem on arrays, strings and two pointers, asked in Amazon, Meta and Wipro interviews.

  • Difficulty: Medium
  • Topics: Arrays, Strings, Two Pointers
  • Asked at: Amazon, Meta, Wipro
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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.

Hints for Sentence Similarity III

  1. Hint 1

    Compare words, not characters — split both sentences first.

  2. Hint 2

    Whatever is inserted is contiguous, so the shorter sentence must survive as a prefix plus a suffix of the longer one.

  3. Hint 3

    Match from the front until the words differ, then from the back, and check the two runs together cover the shorter sentence.

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)

Java

public static boolean areSentencesSimilar(String sentence1, String sentence2) {
    String[] a = sentence1.split(" ");
    String[] b = sentence2.split(" ");
    if (a.length > b.length) {
        String[] t = a;
        a = b;
        b = t;
    }
    int i = 0;
    while (i < a.length && a[i].equals(b[i])) i++;
    int j = 0;
    while (j < a.length - i && a[a.length - 1 - j].equals(b[b.length - 1 - j])) j++;
    return i + j >= a.length;
}

C++

bool areSentencesSimilar(string sentence1, string sentence2) {
    auto split = [](const string& s) {
        vector<string> out;
        string cur;
        for (char ch : s) {
            if (ch == ' ') { out.push_back(cur); cur.clear(); }
            else cur += ch;
        }
        out.push_back(cur);
        return out;
    };
    vector<string> a = split(sentence1), b = split(sentence2);
    if (a.size() > b.size()) swap(a, b);
    int na = (int) a.size(), nb = (int) b.size();
    int i = 0;
    while (i < na && a[i] == b[i]) i++;
    int j = 0;
    while (j < na - i && a[na - 1 - j] == b[nb - 1 - j]) j++;
    return i + j >= na;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings