Skip to content

1813. Sentence Similarity III 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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