• Posts

Problem 1813 Sentence Similarity III

Problem Statement

Link - Problem 1813

Question

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:

Example 2:

Example 3:

Constraints:

• 1 <= 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.

Solution

class Solution {
public:
    vector<string> toStringVec(string& s){
        stringstream ss(s);
        vector<string> ans;
        string w;
        while (ss>>w)
            ans.push_back(w);
        ss.clear();
        return ans;
    }

    bool areSentencesSimilar(string sentence1, string sentence2) {
        auto s1=toStringVec(sentence1), s2=toStringVec(sentence2);
        int n1=s1.size(), n2=s2.size();
        if (n1>n2)
        {
            swap(n1, n2);
            swap(s1, s2);
        }

        int l=0, r2=n2-1, r1=n1-1;

        while(l<n1 && s1[l]==s2[l])
            l++;

        while(r1>=0 && s1[r1]==s2[r2]){
            r1--;
            r2--;
        }

        return r1<l;
    }
};

Complexity Analysis

| Algorithm                                   | Time Complexity | Space Complexity |
| ------------------------------------------- | --------------- | ---------------- |
| Two-pointer traversal with string streaming | O(n)            | O(n)             |

Explanation

Intial Thoughts

The problem can be tackled by breaking down the sentences into individual words and comparing them. The key is to find a way to make the two sentences equal by inserting a sentence into one of them. This can be visualized as finding a common prefix and suffix in the two sentences and checking if the remaining parts can be combined to form a valid sentence. Another approach is to think of it as a string matching problem where we need to find the longest common subsequence between the two sentences.

Intuitive Analysis

To intuitively solve this problem, think of it as trying to fit one sentence into the other by inserting a sentence in between. Start by comparing the two sentences from the beginning and end, and try to find the common words. If the common words are found, check if the remaining parts can be combined to form a valid sentence. Another way to think about it is to consider the words as blocks, and try to fit these blocks together to form a complete sentence. By using this block-fitting approach, we can determine if the two sentences are similar or not.

1. Intuition

• The problem can be approached by comparing the words in both sentences from the start and end, checking for similarities.
• If the shorter sentence is a subsequence of the longer sentence, then they are similar.
• The key insight is to find the common prefix and suffix of the two sentences.
• By comparing the words from the start and end, we can determine if the sentences are similar.
• This approach works because it checks for the possibility of inserting a sentence inside one of the given sentences.
• The time complexity of this approach is O(n), where n is the length of the shorter sentence.
• The space complexity is also O(n) due to the conversion of the sentences into vectors of words.

2. Implementation

• The toStringVec function is used to convert the input sentences into vectors of words using a stringstream.
• The areSentencesSimilar function first converts the input sentences into vectors of words using toStringVec.
• It then checks if the shorter sentence is a subsequence of the longer sentence by comparing the words from the start and end.
• The while loops are used to find the common prefix and suffix of the two sentences.
• The swap function is used to ensure that s1 is always the shorter sentence.
• The function returns true if the sentences are similar and false otherwise.
• The use of l and r1 pointers allows for efficient comparison of the words in the sentences.

Complexity Analysis

Time Complexity:

• The time complexity is O(n) due to the two-pointer traversal in the areSentencesSimilar function, where n represents the length of the shorter sentence. This is because in the worst-case scenario, we traverse both sentences from left to right and right to left once.
• The toStringVec function also contributes to the time complexity as it uses a stringstream to split the input string into a vector of words, resulting in a time complexity of O(m), where m is the total number of characters in the sentence.
• However, since m is proportional to n (the number of words in the sentence), we can simplify the time complexity to O(n), where n is the number of words in the shorter sentence.

Space Complexity:

• The space complexity is O(n) due to the storage of the vector of words for both sentences in the toStringVec function, where n represents the number of words in the longer sentence.
• The use of stringstream objects also contributes to the space complexity, but it is negligible compared to the storage required for the vectors of words.
• The extra variables used in the areSentencesSimilar function, such as l, r1, and r2, have a constant space complexity of O(1) and do not affect the overall space complexity.

Footnote

This question is rated as Medium difficulty.

Hints

One way to look at it is to find one sentence as a concatenation of a prefix and suffix from the other sentence.

Get the longest common prefix between them and the longest common suffix.