Today I have done leetcode's October LeetCoding Challenge with cpp.

October LeetCoding Challenge 6

Description

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.

Solution

vector<string> split(string &s, char spliter) {
  vector<string> result;
  for(int i = 0; i < s.length(); ++i) {
    string st;
    while(i < s.length() && s[i] != spliter) {
      st += s[i];
      i += 1;
    }
    if(st.size()) result.emplace_back(st);
  }
  return result;
}

class Solution {
  bool solve(vector<string> &a, vector<string> &b, int i, int j, int skipStatus) {
    if(i == a.size() && j == b.size()) return true;

    if(i == a.size()) return skipStatus != 2;

    if(j == b.size()) return false;

    if(a[i] != b[j]) {
      if(skipStatus == 2) return false;
      return solve(a, b, i, j + 1, 1);
    }
    if(skipStatus == 1) {
      return solve(a, b, i + 1, j + 1,(skipStatus == 1) ? 2 : skipStatus) || solve(a, b, i, j + 1, 1);
    }
    return solve(a, b, i + 1, j + 1, (skipStatus == 1) ? 2 : skipStatus);
  }
public:
  bool areSentencesSimilar(string s1, string s2) {
    if(s1 == s2) return true;
    vector<string> a = split(s1, ' ');
    vector<string> b = split(s2, ' ');
    if(a.size() > b.size()) swap(a, b);
    return solve(a, b, 0, 0, 0);
  }
};