A sentence is a list of words that are separated by a single space with no leading or trailing spaces. For example, "Hello World", "HELLO", "hello world hello world" are all sentences. Words consist of only uppercase and lowercase English letters.
Two sentences sentence1 and sentence2 are similar if it is possible to insert an arbitrary sentence (possibly empty) inside one of these sentences such that the two sentences become equal. For example, sentence1 = "Hello my name is Jane" and sentence2 = "Hello Jane" can be made equal by inserting "my name is" between "Hello" and "Jane" in sentence2.
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.
Example 4:
Input: sentence1 = "Luky", sentence2 = "Lucccky" Output: false
Constraints:
1 <= sentence1.length, sentence2.length <= 100sentence1 and sentence2 consist of lowercase and uppercase English letters and spaces.sentence1 and sentence2 are separated by a single space.
The description was taken from https://leetcode.com/problems/sentence-similarity-iii/.
#Two Queues#O(M+N) Time, O(M+N) Space
class Solution:
def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:
queue_one = collections.deque(sentence1.split())
queue_two = collections.deque(sentence2.split())
while queue_one and queue_two:
if queue_one[0] != queue_two[0]:
break
queue_one.popleft()
queue_two.popleft() if not queue_one or not queue_two:
return True
while queue_one and queue_two:
if queue_one[-1] != queue_two[-1]:
return False
queue_one.pop()
queue_two.pop()
return True#Two Two-Pointers
#O(M+N) Time, O(M+N) Space
class Solution:
def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:
sentence1 = sentence1.split()
sentence2 = sentence2.split()
one_left, one_right = 0, len(sentence1) - 1
two_left, two_right = 0, len(sentence2) - 1
while one_left <= one_right and two_left <= two_right:
if sentence1[one_left] != sentence2[two_left]:
break
one_left += 1
two_left += 1 if one_left > one_right or two_left > two_right:
return True
while one_right >= one_left and two_right >= two_left:
if sentence1[one_right] != sentence2[two_right]:
return False
one_right -= 1
two_right -= 1
return TrueBased on the given conditions, two words are similar if we can insert more words in the middle of the shorter string to become the longer one.
"My Haley" ->"My name is Haley"
Another way of thinking about this is that two strings are similar if we can delete a suffix and/or prefix to isolate the words that were inserted.
This would be the case if the entire smaller string was deleted for nonnull insertions, or both strings were deleted from a null insertion meaning the two strings are actually the same.
"My Haley" "My name is Haley"
We can solve this by pushing the words from the two input strings into two queues.
By doing this, we will be able to pop off matching prefixes from the left side of the queues and pop off matching suffixes from the right side.
If we are able to delete each word from one of the queues in the process then that means the shorter string was either just a prefix of the larger one, was just a suffix of the larger one, had a matching prefix and suffix to the larger one, or was exactly the same string as the larger one.
Otherwise, it wouldn't be possible to inject words into the smaller one for it to become the larger one.
Let's start by initializing our two queues with both sentence strings.
We'll need to split the sentences into arrays of words so that we are popping matching words instead of matching characters.
queue_one = collections.deque(sentence1.split())
queue_two = collections.deque(sentence2.split())
Now we will remove matching prefixes while we haven't deleted an entire queue yet.
while queue_one and queue_two:
If the leftmost words do not match, we no longer have a matching prefix so we will break.
if queue_one[0] != queue_two[0]:
break
Otherwise, we will pop the current matching prefix word from the beginning of both queues.
queue_one.popleft()
queue_two.popleft()
Once we have broken from the loop, we either broke because one of the queues was empty or the prefixes no longer match.
If it was the former scenario, then that means the entire smaller input string was just a prefix of the larger one or both input strings were the same.
If this was the case, we will return true.
if not queue_one or not queue_two:
return True
Otherwise, we will now pop off matching suffixes from the ends of both queues.
However, in this case, if we find a mismatched element then we will return false.
We just searched for matching prefixes within the previous loop and found a mismatch so if we find a mismatch in suffixes, we now know that these are not similar strings.
while queue_one and queue_two:
if queue_one[-1] != queue_two[-1]:
return False
If these are matching suffixes, however, we will continue popping these matching words off the right side.
queue_one.pop()
queue_two.pop()
If we broke from the loop this time and didn't return false, then that means we deleted an entire queue so the entire smaller input string was just a suffix of the larger one or both input strings were the same.
In this case, we'll return true.
return True
A two-pointer approach can be utilized in place of two queues.
This approach follows the same exact logic as the queue approach, but here we will know if we deleted an entire sentence when a sentence's pointers overlap.
Let's start by splitting the sentences into arrays of words so that we are comparing elements of matching words instead of matching characters.
sentence1 = sentence1.split()
sentence2 = sentence2.split()
We'll then initialize two pointers for each sentence, one at the beginning and one at the end.
one_left, one_right = 0, len(sentence1) - 1
two_left, two_right = 0, len(sentence2) - 1
Now we will exclude matching prefixes while we haven't had two pointers overlap.
while one_left <= one_right and two_left <= two_right:
If the leftmost words do not match, we no longer have a matching prefix so we will break.
if sentence1[one_left] != sentence2[two_left]:
break
Otherwise, we will increment both left pointers.
one_left += 1
two_left += 1
Once we have broken from the loop, we either broke because one of the sentence's pointers overlapped or the prefixes no longer match.
If it was the former scenario, then that means the entire smaller input string was just a prefix of the larger one or both input strings were the same.
If this was the case, we will return true.
if one_left > one_right or two_left > two_right:
return True
Otherwise, we will now exclude matching suffixes from the ends of both sentences.
However, in this case, if we find a mismatched element then we will return false.
We just searched for matching prefixes within the previous loop and found a mismatch so if we find a mismatch in suffixes, we now know that these are not similar strings.
while one_right >= one_left and two_right >= two_left:
if sentence1[one_right] != sentence2[two_right]:
return False
If these are matching suffixes, however, we will continue decrementing our right pointers.
one_right -= 1
two_right -= 1
If we broke from the loop this time and didn't return false, then that means we had an overlap so the entire smaller input string was just a suffix of the larger one or both input strings were the same.
In this case, we'll return true.
return True