Editorial: LeetCode 1813 Sentence Similarity III
https://leetcode.com/problems/sentence-similarity-iii/ from Google
Thinking process:
The problem is asking if it is possible to insert an arbitrary sentence (possibly empty) inside one of these sentences such that the two sentences become equal. So the first thing we can think about is that we must add sentence into the shorter one.
Secondly, since we can only insert “a single sentence”, there’s only few patterns satisfy the requirements. If we can find a sentence which shows in both sentence, we call it a “same sentence”, otherwise, we call it a “diff sentence”. For example, if we have “My name is Haley” and “My Haley”, then “My” and “Haley” are the same sentences, and “name is” is the diff sentence.
With this, the valid patterns are
So in the following code, we’ll use a while loop to find the “same sentence” and the “diff sentence”. Then we only need to make sure we have at most 2 same sentences and at most 1 diff sentence.
Here is the code.
1class Solution {
2public:
3 vector<string> split(string line) {
4 vector <string> tokens;
5 stringstream check1(line);
6 string intermediate;
7 while(getline(check1, intermediate, ' '))
8 {
9 tokens.push_back(intermediate);
10 }
11 return tokens;
12 }
13 bool areSentencesSimilar(string sentence1, string sentence2) {
14 vector<string> s1 = split(sentence1);
15 vector<string> s2 = split(sentence2);
16 int N1 = s1.size(), N2 = s2.size();
17 if (N2 > N1) {
18 swap(N1, N2);
19 swap(s1, s2);
20 }
21 int i1 = 0, i2 = 0;
22 vector<string> same;
23 vector<string> diff;
24 while (i1 < N1 and i2 < N2) {
25 string s = "";
26 string d = "";
27 while (i1 < N1 and i2 < N2) {
28 if (s1[i1] == s2[i2]) {
29 s += s1[i1];
30 i1++, i2++;
31 } else
32 break;
33 }
34 while (i1 < N1 and i2 < N2) {
35 if (s1[i1] != s2[i2]) {
36 d += s1[i1];
37 i1++;
38 } else
39 break;
40 }
41 if (s.size())
42 same.push_back(s);
43 if (d.size())
44 diff.push_back(d);
45 }
46 if (i1 != N1) diff.push_back("");
47 if (i2 != N2) diff.push_back("");
48 return same.size() <= 2 and diff.size() <= 1 and diff.size() <= same.size();
49 }
50};