Sentence Similarity III

Leetcode Problem:

• Sentence Similarity III

Summary

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

Approach

• The approach is to first find the longest common prefix of the two sentences
• If the prefix is empty, the sentences are not similar
• Otherwise, we check if the remaining part of the shorter sentence can be inserted between the words of the longer sentence to make them equal.

Complexity

• O(n), where n is the length of the shorter sentence.

Explanation

• We first find the longest common prefix of the two sentences by iterating through the characters of the sentences
• If the prefix is empty, we return false
• Otherwise, we check if the remaining part of the shorter sentence can be inserted between the words of the longer sentence to make them equal
• We do this by iterating through the remaining part of the shorter sentence and checking if each word matches the corresponding word in the longer sentence
• If we find a mismatch, we return false
• If we reach the end of the remaining part of the shorter sentence without finding a mismatch, we return true.

Solution Code:

class Solution {
public:
    bool areSentencesSimilar(string sentence1, string sentence2) {
        string t;
        if (sentence1.size() < sentence2.size()){
            t = sentence1;
            sentence1 = sentence2;
            sentence2 = t;
        }
        int lastSpace = -1;
        int i = 0;
        for( ; i < sentence2.size(); i++){
            if(sentence2[i] == sentence1[i] && sentence2[i] == ' '){
                lastSpace = i;
            }
            if (sentence1[i] != sentence2[i]) break;
        }
        if (i == sentence2.size() && sentence1[i] == ' ') return true;
        int s1_len = sentence1.size();
        int s2_len = sentence2.size();
        int before_idx = sentence1.size() - (s2_len - lastSpace);
        if (before_idx >= 0 && sentence1[before_idx] != ' ') return false;
        for(i = lastSpace+1; i < s2_len; i++){
            int s1_idx = sentence1.size() - (s2_len - i);
            if(s1_idx >= s1_len) return false;
            if(sentence1[s1_idx] != sentence2[i]) return false;
        }
        return true;
    }
};