Sentence Similarity Using Two Pointers

Problem Statement

Two sentences are similar if you can insert one contiguous run of words (possibly empty) into one of them to get the other. Given sentences s1 and s2, return true if they are similar.

Example

Input:  s1 = "My name is Haley", s2 = "My Haley"
Output: true
Explanation: Insert "name is" into s2.

Two Pointer Approach

Split both sentences into word lists. Use two pointers from the front to count the matching prefix words, and two pointers from the back to count the matching suffix words. They are similar if the matched prefix + suffix covers the shorter sentence entirely.

Complexity

• Time: O(n)
• Space: O(n) for the word lists

Solution Code

Python

def areSentencesSimilar(s1, s2):
    w1, w2 = s1.split(), s2.split()
    if len(w1) > len(w2):
        w1, w2 = w2, w1            # w1 is the shorter list
    i, j = 0, 0
    while i < len(w1) and w1[i] == w2[i]:
        i += 1
    while j < len(w1) - i and w1[len(w1)-1-j] == w2[len(w2)-1-j]:
        j += 1
    return i + j >= len(w1)

Java

boolean areSentencesSimilar(String s1, String s2) {
    String[] w1 = s1.split(" "), w2 = s2.split(" ");
    if (w1.length > w2.length) { String[] tmp = w1; w1 = w2; w2 = tmp; }
    int i = 0, j = 0;
    while (i < w1.length && w1[i].equals(w2[i])) i++;
    while (j < w1.length - i && w1[w1.length-1-j].equals(w2[w2.length-1-j])) j++;
    return i + j >= w1.length;
}

C++

vector<string> splitWords(const string& s) {
    vector<string> w; stringstream ss(s); string x;
    while (ss >> x) w.push_back(x);
    return w;
}
bool areSentencesSimilar(string s1, string s2) {
    vector<string> w1 = splitWords(s1), w2 = splitWords(s2);
    if (w1.size() > w2.size()) swap(w1, w2);
    int i = 0, j = 0;
    while (i < (int)w1.size() && w1[i] == w2[i]) i++;
    while (j < (int)w1.size() - i && w1[w1.size()-1-j] == w2[w2.size()-1-j]) j++;
    return i + j >= (int)w1.size();
}

Key Takeaways

• Match on whole words, not characters.
• Prefix and suffix pointers meet in the middle; the gap must be fully inside the longer sentence.
• Normalising so w1 is the shorter list simplifies the bounds.