Sentence Similarity III
Problem
You are given two sentences sentence1 and sentence2, each a string of space-separated words. The two sentences are similar if it is possible to insert one extra sentence (which may be empty) into exactly one of them — at the start, the end, or between two words — so that the two become identical.
Note that the inserted block must be a single contiguous run of words; you may not sprinkle words into several different places. Return true if the sentences are similar and false otherwise.
sentence1 = "My name is Haley", sentence2 = "My Haley"truesentence2 between "My" and "Haley" and it becomes "My name is Haley", which equals sentence1. The shared prefix "My" and shared suffix "Haley" already cover every word of the shorter sentence.def are_sentences_similar(sentence1, sentence2):
a = sentence1.split()
b = sentence2.split()
i, j = 0, 0
n, m = len(a), len(b)
while i < n and i < m and a[i] == b[i]:
i += 1
while j < n - i and j < m - i and a[n - 1 - j] == b[m - 1 - j]:
j += 1
return i + j >= min(n, m)function areSentencesSimilar(sentence1, sentence2) {
const a = sentence1.split(" ");
const b = sentence2.split(" ");
let i = 0, j = 0;
const n = a.length, m = b.length;
while (i < n && i < m && a[i] === b[i]) i++;
while (j < n - i && j < m - i && a[n - 1 - j] === b[m - 1 - j]) j++;
return i + j >= Math.min(n, m);
}class Solution {
public boolean areSentencesSimilar(String sentence1, String sentence2) {
String[] a = sentence1.split(" ");
String[] b = sentence2.split(" ");
int i = 0, j = 0;
int n = a.length, m = b.length;
while (i < n && i < m && a[i].equals(b[i])) i++;
while (j < n - i && j < m - i && a[n - 1 - j].equals(b[m - 1 - j])) j++;
return i + j >= Math.min(n, m);
}
}bool areSentencesSimilar(string sentence1, string sentence2) {
vector<string> a = split(sentence1), b = split(sentence2);
int i = 0, j = 0;
int n = a.size(), m = b.size();
while (i < n && i < m && a[i] == b[i]) i++;
while (j < n - i && j < m - i && a[n - 1 - j] == b[m - 1 - j]) j++;
return i + j >= min(n, m);
}Explanation
Inserting one contiguous block of words into a sentence keeps everything before the insertion point untouched as a shared prefix, and everything after it untouched as a shared suffix. So if the two sentences are similar, the shorter sentence must equal a prefix of the longer one followed (immediately) by a suffix of the longer one — and the inserted block is exactly the gap in the middle of the longer sentence.
That gives a clean two-pointer test on the word arrays. First walk a pointer i forward from the front while the words at position i agree in both sentences; this counts the length of the common prefix. Then walk a pointer j backward from the end while the words agree; this counts the common suffix. To avoid double-counting a word when one sentence is fully consumed, the suffix scan is bounded so it never reaches past the prefix in either sentence (j < n - i and j < m - i).
The sentences are similar exactly when the prefix and suffix together cover every word of the shorter sentence — that is, i + j >= min(n, m). When that holds, the words of the shorter sentence are split into a front piece and a back piece that both line up with the longer one, and the words sitting between those two pieces in the longer sentence are precisely the block we imagine inserting.
Walking the default example, a = [My, name, is, Haley] and b = [My, Haley]: the prefix scan matches "My" and stops, so i = 1. The suffix scan matches "Haley" and stops, so j = 1. The shorter sentence has length 2 and i + j = 2 >= 2, so the answer is true — and the uncovered middle of the longer sentence, "name is", is what gets inserted.
Each pointer advances at most across all the words once, so the scan runs in O(n + m) time over the words. Splitting the strings into word arrays uses O(n + m) extra space.