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 <= 100Words contain only English letters.Words are separated by single spaces with no leading or trailing space.
Hints for Sentence Similarity III
Hint 1
Compare words, not characters — split both sentences first.
Hint 2
Whatever is inserted is contiguous, so the shorter sentence must survive as a prefix plus a suffix of the longer one.
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
- Split both sentences on spaces and call the shorter list
a, the longerb. - Advance
iwhilea[i]equalsb[i]. - Advance
jwhilea[|a|-1-j]equalsb[|b|-1-j], stopping before the two runs overlap. - 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| - icap 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.