Sentence Similarity III - Solution & Explanation
Problem Statement
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.
Approach Overview
Problem Overview: You are given two sentences. The sentences are considered similar if you can insert a sequence of words into one sentence so that both become identical. The task reduces to checking whether the shorter sentence matches the prefix and suffix of the longer sentence.
Approach 1: Two Pointers Technique (O(n) time, O(n) space)
Split both sentences into arrays of words using a space delimiter. Use the two pointers pattern to match words from the start and from the end. First iterate forward while words match, counting the common prefix. Then iterate backward while words match, counting the common suffix. If the total matched words cover the entire shorter sentence, the remaining unmatched portion in the longer sentence represents the inserted segment. This approach works because valid similarity only allows extra words in the middle of one sentence.
The algorithm performs sequential comparisons across the word arrays, which keeps the complexity linear. It only stores the tokenized sentences, so space complexity is proportional to the number of words. This is the most practical solution and commonly used in interview discussions involving array traversal and string manipulation.
Approach 2: Dynamic Programming (O(n*m) time, O(n*m) space)
A dynamic programming approach models the problem as finding the longest common subsequence (LCS) between the two word arrays. Build a DP table where dp[i][j] stores the LCS length for the first i words of one sentence and the first j words of the other. If the LCS length equals the size of the shorter sentence and the matched words appear as a prefix and suffix combination, the sentences are similar. This method systematically explores all alignments of words.
Although DP guarantees correctness, it performs unnecessary work because the allowed insertion pattern only occurs in the middle of the sentence. The time and space cost grows with the product of both sentence lengths, which makes it less efficient than the pointer-based method.
Recommended for interviews: The two pointers technique is the expected solution. It demonstrates that you recognize the structural constraint: only the middle section can differ. Explaining a brute-force or DP idea first shows problem exploration, but implementing the O(n) two-pointer scan proves strong algorithmic judgment.
Approach 1: Two Pointers Technique
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.
Complexity
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.
Approach 2: Dynamic Programming
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.
Complexity
Time Complexity: O(n*m)
Space Complexity: O(n*m)
Approach 3: 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 iwords1[i] is equal to words2[i], and if so, pointer continues to move right; then we loop to check whether jwords1[m - 1 - j] is equal to words2[n - 1 - j], and if so, pointer 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.
Code
Python
Java
C++
Go
TypeScript
JavaScript
Complexity Comparison
| 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) |
| Two Pointers | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pointers Technique | O(n) | O(n) | Best choice when comparing word sequences and only a middle insertion is allowed |
| Dynamic Programming (LCS) | O(n*m) | O(n*m) | Useful for learning or when solving generalized subsequence similarity problems |
Video Solution
Sentence Similarity III - Leetcode 1813 - Python • NeetCodeIO • 11,935 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Sentence Similarity III easy or hard?
Sentence Similarity III Python/Java solution
How to solve Sentence Similarity III in O(n)?
What is the best approach for Sentence Similarity III?
Is Sentence Similarity III asked at Google/Amazon/Meta?
What data structure is used in Sentence Similarity III?
What is the time complexity of Sentence Similarity III?
Ready to solve this problem?
Practice Sentence Similarity III with our built-in code editor and test cases.
Practice on FleetCode