1813. Sentence Similarity III LeetCode Solution

In this guide, you will get 1813. Sentence Similarity III LeetCode Solution with the best time and space complexity. The solution to Sentence Similarity III problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Sentence Similarity III solution in C++
Sentence Similarity III solution in Java
Sentence Similarity III solution in Python
Additional Resources

1813. Sentence Similarity III LeetCode Solution image

Problem Statement of 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:

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

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

1813. Sentence Similarity III LeetCode Solution in C++

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 m = words1.size();
    const int n = words2.size();
    if (m > n)
      return areSentencesSimilar(sentence2, sentence1);

    int i = 0;  // words1's index
    while (i < m && words1[i] == words2[i])
      ++i;
    while (i < m && words1[i] == words2[i + n - m])
      ++i;

    return i == m;
  }

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

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

    return words;
  }
};
/* code provided by PROGIEZ */

1813. Sentence Similarity III LeetCode Solution in Java

class Solution {
  public boolean areSentencesSimilar(String sentence1, String sentence2) {
    if (sentence1.length() == sentence2.length())
      return sentence1.equals(sentence2);

    String[] words1 = sentence1.split(" ");
    String[] words2 = sentence2.split(" ");
    final int m = words1.length;
    final int n = words2.length;
    if (m > n)
      return areSentencesSimilar(sentence2, sentence1);

    int i = 0; // words1's index
    while (i < m && words1[i].equals(words2[i]))
      ++i;
    while (i < m && words1[i].equals(words2[i + n - m]))
      ++i;

    return i == m;
  }
}
// code provided by PROGIEZ

1813. Sentence Similarity III LeetCode Solution in Python

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

    words1 = sentence1.split()
    words2 = sentence2.split()
    m, n = map(len, (words1, words2))
    if m > n:
      return self.areSentencesSimilar(sentence2, sentence1)

    i = 0  # words1's index
    while i < m and words1[i] == words2[i]:
      i += 1
    while i < m and words1[i] == words2[i + n - m]:
      i += 1

    return i == m
 # code by PROGIEZ