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" and s2 = "Hello my name is Jane" can be made equal by inserting "my name is" between "Hello" and "Jane" in s1.s1 = "Frog cool" and s2 = "Frogs are cool" are not similar, since although there is a sentence "s are" inserted into s1, 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 <= 100sentence1 and sentence2 consist of lowercase and uppercase English letters and spaces.sentence1 and sentence2 are separated by a single space.The Two Pointers technique involves using two indices that move towards each other from the start and end of the lists. This approach effectively captures the prefixes and suffixes.
By using two pointers, we move from the start to the first words that don't match and from the end to the first words that also don't match. If the pointers end up crossing or are equal, the sentences are considered similar. We exploit the fact that any dissimilar portion in the middle, if any, can be 'inserted'.
This solution leverages strtok to split the strings into words and uses two pointers, i and j, to iterate from the left and right. The solution successfully checks if the subsequences align in an overlapping manner.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + m), where n and m are the lengths of sentence1 and sentence2 respectively.
Space Complexity: O(n + m) for storing words.
Another approach is to utilize a dynamic programming table to store sub-problems results. You can construct a DP table where dp[i][j] indicates whether the first i words from sentence1 can match the first j words from sentence2. This could be expanded using insertion strategies for any non-matching sub-sequences.
This approach relies more on systematic computation than geometric traversal, but can be more memory intensive.
This solution uses dynamic programming where a table is constructed to store sub-computations. The logic draws from comparing and setting DP cells based on direct match or feasibility of insertion.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n*m)
Space Complexity: O(n*m)
| Approach | Complexity |
|---|---|
| Two Pointers Technique | Time Complexity: O(n + m), where n and m are the lengths of sentence1 and sentence2 respectively. |
| Dynamic Programming | Time Complexity: O(n*m) |
Sentence Similarity III - Leetcode 1813 - Python • NeetCodeIO • 10,674 views views
Watch 9 more video solutions →Practice Sentence Similarity III with our built-in code editor and test cases.
Practice on FleetCode