1813. Sentence Similarity III

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.

Approach 01:

class Solution {
public:
    bool areSentencesSimilar(string sentence1, string sentence2) {
        if (sentence1.length() == sentence2.length())
            return sentence1 == sentence2;

        vector<string> words1 = split(sentence1);
        vector<string> words2 = split(sentence2);
        const int size1 = words1.size();
        const int size2 = words2.size();
        
        if (size1 > size2)
            return areSentencesSimilar(sentence2, sentence1);

        int index = 0;  // words1's index
        while (index < size1 && words1[index] == words2[index])
            ++index;
        while (index < size1 && words1[index] == words2[index + size2 - size1])
            ++index;

        return index == size1;
    }

private:
    vector<string> split(const string& sentence) {
        vector<string> words;
        istringstream iss(sentence);

        for (string word; iss >> word;)
            words.push_back(word);

        return words;
    }
};

class Solution:
    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:
        if len(sentence1) == len(sentence2):
            return sentence1 == sentence2

        words1 = self.split(sentence1)
        words2 = self.split(sentence2)
        size1 = len(words1)
        size2 = len(words2)

        if size1 > size2:
            return self.areSentencesSimilar(sentence2, sentence1)

        index = 0  # words1's index
        while index < size1 and words1[index] == words2[index]:
            index += 1
        while index < size1 and words1[index] == words2[index + size2 - size1]:
            index += 1

        return index == size1

    def split(self, sentence: str) -> list:
        return sentence.split()

Time Complexity

• Splitting the sentences:

  The split function iterates through each character of the sentence to extract words. The time taken to split both sentences is \(O(n + m)\), where \(n\) is the length of sentence1 and \(m\) is the length of sentence2.

• Comparing words:

  The function then compares words from both vectors. The worst-case scenario occurs when all words need to be compared, which can take \(O(\min(size1, size2))\) time, where size1 and size2 are the number of words in words1 and words2, respectively.

• Overall Time Complexity:

  The overall time complexity is \(O(n + m)\), where \(n\) and \(m\) are the lengths of sentence1 and sentence2.

Space Complexity

• Auxiliary Space:

  The space used by the split function requires space for storing the words of both sentences. Therefore, the space complexity is \(O(n + m)\), where \(n\) and \(m\) are the lengths of sentence1 and sentence2.

• Overall Space Complexity:

  The overall space complexity is \(O(n + m)\) due to the storage of the words from both sentences in separate vectors.