Leetcode 1813. Sentence Similarity III Solution

Problem Explanation

We are given two sentences sentence1 and sentence2. A sentence is a list of words that are separated by a single space with no leading or trailing spaces. The words consist of only uppercase and lowercase English letters. Our task is to determine if two sentences are similar or not.

Two sentences 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. In other words, we can match some continuous words from the start of both sentences, and some from the end. If the total matched words equal the size of the smaller sentence, we can say that both sentences are similar.

We are required to implement a function bool areSentencesSimilar(string sentence1, string sentence2) that returns true if the given sentences are similar, otherwise returns false.

Approach

We can tackle this problem by following these steps:

1. Split the sentences into words, creating two vector of strings (e.g., words1 and words2 representing sentence1 and sentence2 respectively).
2. If words1 is longer than words2, swap them.
3. Initialize i to 0 (to serve as an index for words1).
4. Iterate through both words1 and words2 from start to end. If the words match, increment i.
5. Now, reset the loop and iterate through words1 and words2 from the position i to end. If the words match, increment the index i.
6. Check if the total matched words (the value of i) is equal to words1 size (smaller sentences). If yes, the sentences are similar, so return true. Otherwise, return false.

Let's understand it better with an example:

Example:

sentence1 = "My name is Haley", sentence2 = "My Haley"

1. Split the sentences: words1 = ["My", "name", "is", "Haley"] words2 = ["My", "Haley"]
2. words1 has length 4, words2 has length 2. So no need to swap.
3. Initialize the index i to 0.
4. Iterate through both words1 and words2 from start.
   • words1[0] and words2[0] both are "My", so increment i to 1.
5. Reset the loop and iterate through words1 and words2 from i to end.
   • words1[1] and words2[2-1] both are "Haley", so increment i to 2.
6. Check if the total matched words (i=2) is equal to words1 size (2). As it is equal, both sentences are similar, so return true.

Solution

Python

1class Solution:
2    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:
3        words1 = sentence1.split()
4        words2 = sentence2.split()
5        
6        if len(words1) > len(words2):
7            words1, words2 = words2, words1
8
9        i = 0
10        while i < len(words1) and words1[i] == words2[i]:
11            i += 1
12
13        while i < len(words1) and words1[i] == words2[i + len(words2) - len(words1)]:
14            i += 1
15
16        return i == len(words1)

Java

1import java.util.Arrays;
2import java.util.List;
3
4class Solution {
5    public boolean areSentencesSimilar(String sentence1, String sentence2) {
6        List<String> words1 = Arrays.asList(sentence1.split(" "));
7        List<String> words2 = Arrays.asList(sentence2.split(" "));
8
9        if (words1.size() > words2.size()) {
10            List<String> temp = words1;
11            words1 = words2;
12            words2 = temp;
13        }
14
15        int i = 0;
16        while (i < words1.size() && words1.get(i).equals(words2.get(i))) {
17            i++;
18        }
19
20        while (i < words1.size() && words1.get(i).equals(words2.get(i + words2.size() - words1.size()))) {
21            i++;
22        }
23
24        return i == words1.size();
25    }
26}

JavaScript

1class Solution {
2    areSentencesSimilar(sentence1, sentence2) {
3        const words1 = sentence1.split(' ');
4        const words2 = sentence2.split(' ');
5
6        if (words1.length > words2.length) {
7            [words1, words2] = [words2, words1];
8        }
9
10        let i = 0;
11        while (i < words1.length && words1[i] === words2[i]) {
12            i++;
13        }
14
15        while (i < words1.length && words1[i] === words2[i + words2.length - words1.length]) {
16            i++;
17        }
18
19        return i === words1.length;
20    }
21}

C++

1#include <algorithm>
2#include <sstream>
3#include <vector>
4
5class Solution {
6 public:
7  bool areSentencesSimilar(std::string sentence1, std::string sentence2) {
8    std::vector<std::string> words1 = split(sentence1);
9    std::vector<std::string> words2 = split(sentence2);
10
11    if (words1.size() > words2.size())
12      std::swap(words1, words2);
13
14    int i = 0;
15    while (i < words1.size() && words1[i] == words2[i])
16      ++i;
17
18    while (i < words1.size() && words1[i] == words2[i + words2.size() - words1.size()])
19      ++i;
20
21    return i == words1.size();
22  }
23
24 private:
25  std::vector<std::string> split(const std::string& sentence) {
26    std::vector<std::string> words;
27    std::istringstream iss(sentence);
28
29    for (std::string s; iss >> s;)
30      words.push_back(s);
31
32    return words;
33  }
34};

C#

1using System.Collections.Generic;
2using System.Linq;
3
4public class Solution {
5    public bool AreSentencesSimilar(string sentence1, string sentence2) {
6        List<string> words1 = sentence1.Split(" ").ToList();
7        List<string> words2 = sentence2.Split(" ").ToList();
8
9        if (words1.Count > words2.Count) {
10            List<string> temp = words1;
11            words1 = words2;
12            words2 = temp;
13        }
14
15        int i = 0;
16        while (i < words1.Count && words1[i] == words2[i]) {
17            i++;
18        }
19
20        while (i < words1.Count && words1[i] == words2[i + words2.Count - words1.Count]) {
21            i++;
22        }
23
24        return i == words1.Count;
25    }
26}

Conclusion

The above solutions work efficiently in finding if two sentences are similar or not. The time complexity of these solutions is O(min(N,M)), where N and M are the length of words1 and words2. In the worst-case scenario, we would iterate min(N, M) words from the start and end of the sentences for comparison. The space complexity is also O(min(N,M)), as we are storing the sentences in the form of lists (words1 and words2).

By following this approach, you can accurately find out if two sentences are similar in various programming languages like Python, JavaScript, Java, C++, and C#.