Leetcode 1813: Sentence Similarity III
You are given two sentences, sentence1 and sentence2, which consist of words separated by spaces. Two sentences are considered similar if you can insert any number of words (including none) into one of the sentences to make them identical. The inserted words must be separated by spaces.
Problem
Approach
Steps
Complexity
Input: Each input consists of two strings, sentence1 and sentence2, which are sentences made up of words separated by spaces.
Example: sentence1 = "I am learning", sentence2 = "I learning"
Constraints:
• sentence1.length, sentence2.length <= 100
• sentence1 and sentence2 consist of lowercase and uppercase English letters and spaces.
• The words in sentence1 and sentence2 are separated by a single space.
Output: Return true if the sentences can be made equal by inserting words into one of the sentences. Otherwise, return false.
Example: Output: true
Constraints:
• The output should be a boolean indicating if the sentences are similar.
Goal: To check if one sentence can be transformed into the other by inserting words in between.
Steps:
• Split both sentence1 and sentence2 into individual words.
• Find the longest common prefix and suffix between the two lists of words.
• If one sentence can be made equal by inserting words from the other sentence in the middle, return true. Otherwise, return false.
Goal: The input sentences will always have valid characters and will follow the constraints outlined.
Steps:
• Both sentence1 and sentence2 will contain only letters and spaces.
• Both sentences will not have leading or trailing spaces.
Assumptions:
• The sentences consist of only uppercase and lowercase English letters and spaces.
• The words in the sentences are separated by a single space.
• Input: sentence1 = "I am learning", sentence2 = "I learning"
• Explanation: The words 'I' and 'learning' are common in both sentences. You can insert 'am' between them to make the sentences identical.
• Input: sentence1 = "Hi there", sentence2 = "Hi"
• Explanation: The word 'Hi' is common in both sentences, and we can insert 'there' after 'Hi' in sentence2 to make the sentences identical.
Approach: To determine if one sentence can be made identical to another, we will check for common prefix and suffix of words and allow insertion of words in between.
Observations:
• We can solve this problem by splitting the sentences into words.
• Then, we can compare common prefixes and suffixes of the two sentences.
• If the two sentences have a common prefix and suffix, we can insert the remaining words from one sentence into the other to make them identical.
Steps:
• Split sentence1 and sentence2 into a list of words.
• Find the longest common prefix and suffix between the two lists.
• Check if the remaining words in both lists can be inserted into each other.
Empty Inputs:
• The sentences will not be empty as per the given constraints.
Large Inputs:
• The solution should work efficiently within the constraint that sentence length is <= 100.
Special Values:
• Consider cases where one sentence is a subset of the other or where the sentences have no common words.
Constraints:
• The input strings will not contain leading or trailing spaces.
bool areSentencesSimilar(string s1, string s2) {
deque<string> a, b;
string tmp = "";
for(char c: s1) {
if(c == ' ') a.push_back(tmp), tmp = "";
else tmp += c;
}
a.push_back(tmp), tmp = "";
for(char c: s2) {
if(c == ' ') b.push_back(tmp), tmp = "";
else tmp += c;
}
b.push_back(tmp), tmp = "";
while(a.size() != 0 && b.size() != 0 && (a.front() == b.front())) a.pop_front(), b.pop_front();
while(a.size() != 0 && b.size() != 0 && (a.back() == b.back())) a.pop_back(), b.pop_back();
if(a.size() == 0 || b.size() == 0) return true;
return false;
}
1 : Function Definition
bool areSentencesSimilar(string s1, string s2) {
This line defines the function `areSentencesSimilar`, which takes two strings `s1` and `s2` as input and returns a boolean value indicating whether the two sentences are similar based on their words.
2 : Deque Initialization
deque<string> a, b;
Two deques `a` and `b` are initialized to store words from the two input sentences `s1` and `s2`.
3 : Temporary Variable
string tmp = "";
A temporary string `tmp` is initialized to accumulate characters of each word as we traverse the sentences.
4 : Splitting Sentence 1
for(char c: s1) {
This loop iterates over each character of the first sentence `s1` to split it into individual words.
5 : Word Separation
if(c == ' ') a.push_back(tmp), tmp = "";
When a space is encountered, the current word `tmp` is added to deque `a`, and `tmp` is reset to an empty string for the next word.
6 : Word Accumulation
else tmp += c;
If the character is not a space, it is added to the temporary string `tmp`.
7 : Final Word in Sentence 1
a.push_back(tmp), tmp = "";
After the loop ends, the last word in `tmp` is pushed to deque `a`.
8 : Splitting Sentence 2
for(char c: s2) {
This loop iterates over each character of the second sentence `s2` to split it into individual words.
9 : Word Separation for Sentence 2
if(c == ' ') b.push_back(tmp), tmp = "";
When a space is encountered in the second sentence, the current word `tmp` is added to deque `b`, and `tmp` is reset.
10 : Word Accumulation for Sentence 2
else tmp += c;
If the character is not a space, it is added to the temporary string `tmp`.
11 : Final Word in Sentence 2
b.push_back(tmp), tmp = "";
The last word of `tmp` is added to deque `b` after the loop ends.
12 : Removing Matching Words from Front
while(a.size() != 0 && b.size() != 0 && (a.front() == b.front())) a.pop_front(), b.pop_front();
This loop compares and removes matching words from the front of both deques `a` and `b`.
13 : Removing Matching Words from Back
while(a.size() != 0 && b.size() != 0 && (a.back() == b.back())) a.pop_back(), b.pop_back();
This loop compares and removes matching words from the back of both deques `a` and `b`.
14 : Final Check for Similarity
if(a.size() == 0 || b.size() == 0) return true;
If either deque is empty (indicating all words have been matched), the function returns `true`, indicating the sentences are similar.
15 : Return False
return false;
If neither deque is empty, the sentences are not similar, and the function returns `false`.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n), where n is the number of words in the longest sentence.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n), where n is the number of words in the sentences, since we need to store the words in separate lists.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus