Sentence Similarity III
MedPrompt
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"ands2 = "Hello my name is Jane"can be made equal by inserting"my name is"between"Hello"and"Jane"in s1.s1 = "Frog cool"ands2 = "Frogs are cool"are not similar, since although there is a sentence"s are"inserted intos1, 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.
Example 1:
Input: sentence1 = "My name is Haley", sentence2 = "My Haley"
Output: true
Explanation:
sentence2 can be turned to sentence1 by inserting "name is" between "My" and "Haley".
Example 2:
Input: sentence1 = "of", sentence2 = "A lot of words"
Output: false
Explanation:
No single sentence can be inserted inside one of the sentences to make it equal to the other.
Example 3:
Input: sentence1 = "Eating right now", sentence2 = "Eating"
Output: true
Explanation:
sentence2 can be turned to sentence1 by inserting "right now" at the end of the sentence.
Constraints:
1 <= sentence1.length, sentence2.length <= 100sentence1andsentence2consist of lowercase and uppercase English letters and spaces.- The words in
sentence1andsentence2are separated by a single space.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach systematically checks every possible way the shorter sentence can be split into a prefix and a suffix. For each split, it verifies if the longer sentence starts with that prefix and ends with that suffix.
Algorithm
- Split
sentence1andsentence2into word arrays,words1andwords2. - To simplify, ensure
words1is the shorter array by swapping them if necessary. Letn1be the length ofwords1andn2be the length ofwords2. - Iterate through all possible split points in
words1. A split pointi(from0ton1) divideswords1into a prefix of lengthiand a suffix of lengthn1 - i. - For each split point
i:- Check if the first
iwords ofwords1are identical to the firstiwords ofwords2. - Check if the last
n1 - iwords ofwords1are identical to the lastn1 - iwords ofwords2. - If both conditions are true, it means we've found a valid configuration. Return
true.
- Check if the first
- If the loop completes without finding any valid split point, the sentences are not similar. Return
false.
Walkthrough
First, we split both sentences into arrays of words. To simplify the logic, we ensure one array (words1) is always the shorter one (or equal in length).
The core idea is that if the sentences are similar, the shorter sentence (words1) must be formed by a prefix and a suffix of the longer sentence (words2). We can iterate through all possible split points of words1. A split point i (from 0 to words1.length) divides words1 into prefix = words1[0...i-1] and suffix = words1[i...n1-1].
For each split, we check two conditions:
- Does
words2start with theprefixfromwords1? - Does
words2end with thesuffixfromwords1?
If both conditions are met for any split point, it means we can form words2 by inserting words into words1 at that split point. We then return true. If we check all possible splits and none satisfy the conditions, the sentences are not similar, and we return false.
class Solution { public boolean areSentencesSimilar(String sentence1, String sentence2) { String[] words1 = sentence1.split(" "); String[] words2 = sentence2.split(" "); // Ensure words1 is the shorter or equal length array if (words1.length > words2.length) { String[] temp = words1; words1 = words2; words2 = temp; } int n1 = words1.length; int n2 = words2.length; // Iterate through all possible split points in words1 for (int i = 0; i <= n1; i++) { // Split words1 into a prefix (length i) and a suffix (length n1-i) boolean prefixMatch = true; for (int j = 0; j < i; j++) { if (!words1[j].equals(words2[j])) { prefixMatch = false; break; } } if (!prefixMatch) { continue; } boolean suffixMatch = true; int suffixLen = n1 - i; for (int j = 0; j < suffixLen; j++) { if (!words1[i + j].equals(words2[n2 - suffixLen + j])) { suffixMatch = false; break; } } if (prefixMatch && suffixMatch) { return true; } } return false; }}Complexity
Time
O(L1 + L2 + n1^2 * W), where `L1` and `L2` are the lengths of the sentences, `n1` is the number of words in the shorter sentence, and `W` is the maximum length of a word. The `split` operation takes `O(L1 + L2)`. The nested loops lead to `O(n1^2 * W)` complexity because for each of `n1` splits, we perform checks that can take up to `O(n1 * W)` time.
Space
O(L1 + L2), where L1 and L2 are the lengths of the input sentences. This space is required to store the arrays of words.
Trade-offs
Pros
Conceptually straightforward and easy to understand.
Directly models the problem definition by trying all possible insertion points.
Cons
Inefficient due to nested loops and repeated comparisons.
For each of the
n1+1split points, it re-scans parts of the arrays, leading to a higher time complexity than necessary.
This approach uses a greedy strategy with two pointers to efficiently find the longest common prefix and the longest common suffix between the two sentences. If these two parts account for all the words in the shorter sentence, they are similar.
Algorithm
- Split
sentence1andsentence2into word arrays,words1andwords2. - If
words1is longer thanwords2, make a recursive call with swapped arguments to ensurewords1is always the shorter array. Letn1be the length ofwords1andn2be the length ofwords2. - Initialize a pointer
i = 0. Incrementiwhilei < n1andwords1[i]equalswords2[i]. After this loop,iholds the length of the common prefix. - Initialize a pointer
j = 0. Incrementjwhilej < n1 - iandwords1[n1 - 1 - j]equalswords2[n2 - 1 - j]. This finds the length of the common suffix, considering only the parts of the arrays not matched by the prefix. - The sentences are similar if and only if the sum of the lengths of the common prefix and suffix equals the length of the shorter sentence. Return the result of
i + j == n1.
Walkthrough
Similar to the first approach, we begin by splitting the sentences into word arrays and ensuring words1 is the shorter one. Instead of iterating through all split points, we can find the single required split point greedily. The core observation is that any valid arrangement must consist of a common prefix and a common suffix.
We use a pointer i starting from the beginning of both arrays to find the length of the longest common prefix. We advance i as long as words1[i] equals words2[i].
Then, we use another pointer j starting from the end of both arrays to find the length of the longest common suffix. We advance j as long as the words at the end match. Crucially, we only consider the parts of the sentences not already part of the common prefix.
Finally, if the total length of the common prefix (i) and the common suffix (j) is equal to the total number of words in the shorter sentence (n1), it means every word in the shorter sentence has been matched. This confirms the sentences are similar.
class Solution { public boolean areSentencesSimilar(String sentence1, String sentence2) { String[] words1 = sentence1.split(" "); String[] words2 = sentence2.split(" "); if (words1.length > words2.length) { return areSentencesSimilar(sentence2, sentence1); } int n1 = words1.length; int n2 = words2.length; int i = 0; // length of common prefix while (i < n1 && words1[i].equals(words2[i])) { i++; } int j = 0; // length of common suffix // We only check the part of words1 not covered by the prefix while (j < n1 - i && words1[n1 - 1 - j].equals(words2[n2 - 1 - j])) { j++; } // If the length of the common prefix and suffix equals the length of the shorter sentence return i + j == n1; }}Complexity
Time
O(L1 + L2), where `L1` and `L2` are the lengths of the sentences. The `split` operation takes `O(L1 + L2)`. The two `while` loops together iterate through the shorter word array at most once. The total time for loops is `O(n1 * W)` (where `n1` is word count and `W` is max word length), which is bounded by `O(L1)`. Thus, the overall complexity is dominated by the string splitting.
Space
O(L1 + L2), where L1 and L2 are the lengths of the input sentences. This space is used to store the word arrays.
Trade-offs
Pros
Highly efficient with a single pass from both ends of the arrays.
Optimal time and space complexity for this problem.
The logic is clean and avoids redundant computations.
Cons
The logic with two pointers and careful indexing might be slightly less intuitive at first glance compared to the brute-force method.
Solutions
Solution
class Solution { public boolean areSentencesSimilar ( String sentence1 , String sentence2 ) { var words1 = sentence1 . split ( " " ); var words2 = sentence2 . split ( " " ); if ( words1 . length < words2 . length ) { var t = words1 ; words1 = words2 ; words2 = t ; } int m = words1 . length , n = words2 . length ; int i = 0 , j = 0 ; while ( i < n && words1 [ i ]. equals ( words2 [ i ])) { ++ i ; } while ( j < n && words1 [ m - 1 - j ]. equals ( words2 [ n - 1 - j ])) { ++ j ; } return i + j >= n ; } }function areSentencesSimilar ( sentence1 , sentence2 ) { const [ words1 , words2 ] = [ sentence1 . split ( ' ' ), sentence2 . split ( ' ' )]; const [ m , n ] = [ words1 . length , words2 . length ]; if ( m > n ) return areSentencesSimilar ( sentence2 , sentence1 ); let [ l , r ] = [ 0 , 0 ]; for ( let i = 0 ; i < n ; i ++ ) { if ( l === i && words1 [ i ] === words2 [ i ]) l ++ ; if ( r === i && words2 [ n - i - 1 ] === words1 [ m - r - 1 ]) r ++ ; } return l + r >= m ; }class Solution {public: bool areSentencesSimilar(string sentence1, string sentence2) { auto words1 = split(sentence1, ' '); auto words2 = split(sentence2, ' '); if (words1.size() < words2.size()) { swap(words1, words2); } int m = words1.size(), n = words2.size(); int i = 0, j = 0; while (i < n && words1[i] == words2[i]) { ++i; } while (j < n && words1[m - 1 - j] == words2[n - 1 - j]) { ++j; } return i + j >= n; } vector<string> split(string &s, char delim) { stringstream ss(s); string item; vector<string> res; while (getline(ss, item, delim)) { res.emplace_back(item); } return res; }};class Solution : def areSentencesSimilar ( self , sentence1 : str , sentence2 : str ) -> bool : words1 , words2 = sentence1 . split (), sentence2 . split () m , n = len ( words1 ), len ( words2 ) if m < n : words1 , words2 = words2 , words1 m , n = n , m i = j = 0 while i < n and words1 [ i ] == words2 [ i ]: i += 1 while j < n and words1 [ m - 1 - j ] == words2 [ n - 1 - j ]: j += 1 return i + j >= nVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.