1813. Sentence Similarity III
Description
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 <= 100
sentence1
andsentence2
consist of lowercase and uppercase English letters and spaces.- The words in
sentence1
andsentence2
are separated by a single space.
Solutions
Solution 1: Two Pointers
We split the two sentences into two word arrays words1
and words2
by spaces. Let the lengths of words1
and words2
be $m$ and $n$, respectively, and assume that $m \ge nn.
We use two pointers $i$ and $j$, initially $i = j = 0$. Next, we loop to check whether words1[i]
is equal to words2[i]
, and if so, pointer $i$ continues to move right; then we loop to check whether words1[m - 1 - j]
is equal to words2[n - 1 - j]
, and if so, pointer $j$ continues to move right.
After the loop, if $i + j \ge n$, it means that the two sentences are similar, and we return true
; otherwise, we return false
.
The time complexity is $O(L)$, and the space complexity is $O(L)$, where $L$ is the sum of the lengths of the two sentences.
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
|