# Sentence Similarity III
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/sentence-similarity-iii)
Canonical: https://scaleengineer.com/dsa/problems/sentence-similarity-iii
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Array, String
---
## Problem
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:**

**Input:** sentence1 = "My name is Haley", sentence2 = "My Haley"

**Output:** true

**Explanation:**

`sentence2` can be turned to `sentence1` by inserting "name is" between "My" and "Haley".

**Example 2:**

**Input:** sentence1 = "of", sentence2 = "A lot of words"

**Output:** false

**Explanation:**

No single sentence can be inserted inside one of the sentences to make it equal to the other.

**Example 3:**

**Input:** sentence1 = "Eating right now", sentence2 = "Eating"

**Output:** true

**Explanation:**

`sentence2` can be turned to `sentence1` by inserting "right now" at the end of the sentence.

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

# Approaches
## Brute-Force by Checking All Split Points
This approach systematically checks every possible way the shorter sentence can be split into a prefix and a suffix. For each split, it verifies if the longer sentence starts with that prefix and ends with that suffix.
**Time:** O(L1 + L2 + n1^2 * W), where `L1` and `L2` are the lengths of the sentences, `n1` is the number of words in the shorter sentence, and `W` is the maximum length of a word. The `split` operation takes `O(L1 + L2)`. The nested loops lead to `O(n1^2 * W)` complexity because for each of `n1` splits, we perform checks that can take up to `O(n1 * W)` time. · **Space:** O(L1 + L2), where L1 and L2 are the lengths of the input sentences. This space is required to store the arrays of words.
**Pros:** Conceptually straightforward and easy to understand.; Directly models the problem definition by trying all possible insertion points.
**Cons:** Inefficient due to nested loops and repeated comparisons.; For each of the `n1+1` split points, it re-scans parts of the arrays, leading to a higher time complexity than necessary.
### Explanation
First, we split both sentences into arrays of words. To simplify the logic, we ensure one array (`words1`) is always the shorter one (or equal in length).

The core idea is that if the sentences are similar, the shorter sentence (`words1`) must be formed by a prefix and a suffix of the longer sentence (`words2`). We can iterate through all possible split points of `words1`. A split point `i` (from 0 to `words1.length`) divides `words1` into `prefix = words1[0...i-1]` and `suffix = words1[i...n1-1]`.

For each split, we check two conditions:
1.  Does `words2` start with the `prefix` from `words1`?
2.  Does `words2` end with the `suffix` from `words1`?

If both conditions are met for any split point, it means we can form `words2` by inserting words into `words1` at that split point. We then return `true`. If we check all possible splits and none satisfy the conditions, the sentences are not similar, and we return `false`.

```java
class Solution {
    public boolean areSentencesSimilar(String sentence1, String sentence2) {
        String[] words1 = sentence1.split(" ");
        String[] words2 = sentence2.split(" ");

        // Ensure words1 is the shorter or equal length array
        if (words1.length > words2.length) {
            String[] temp = words1;
            words1 = words2;
            words2 = temp;
        }

        int n1 = words1.length;
        int n2 = words2.length;

        // Iterate through all possible split points in words1
        for (int i = 0; i <= n1; i++) {
            // Split words1 into a prefix (length i) and a suffix (length n1-i)

            boolean prefixMatch = true;
            for (int j = 0; j < i; j++) {
                if (!words1[j].equals(words2[j])) {
                    prefixMatch = false;
                    break;
                }
            }

            if (!prefixMatch) {
                continue;
            }

            boolean suffixMatch = true;
            int suffixLen = n1 - i;
            for (int j = 0; j < suffixLen; j++) {
                if (!words1[i + j].equals(words2[n2 - suffixLen + j])) {
                    suffixMatch = false;
                    break;
                }
            }

            if (prefixMatch && suffixMatch) {
                return true;
            }
        }

        return false;
    }
}
```
### Algorithm
*   Split `sentence1` and `sentence2` into word arrays, `words1` and `words2`.
*   To simplify, ensure `words1` is the shorter array by swapping them if necessary. Let `n1` be the length of `words1` and `n2` be the length of `words2`.
*   Iterate through all possible split points in `words1`. A split point `i` (from `0` to `n1`) divides `words1` into a prefix of length `i` and a suffix of length `n1 - i`.
*   For each split point `i`:
    *   Check if the first `i` words of `words1` are identical to the first `i` words of `words2`.
    *   Check if the last `n1 - i` words of `words1` are identical to the last `n1 - i` words of `words2`.
    *   If both conditions are true, it means we've found a valid configuration. Return `true`.
*   If the loop completes without finding any valid split point, the sentences are not similar. Return `false`.

## Optimized Two-Pointer Approach
This approach uses a greedy strategy with two pointers to efficiently find the longest common prefix and the longest common suffix between the two sentences. If these two parts account for all the words in the shorter sentence, they are similar.
**Time:** O(L1 + L2), where `L1` and `L2` are the lengths of the sentences. The `split` operation takes `O(L1 + L2)`. The two `while` loops together iterate through the shorter word array at most once. The total time for loops is `O(n1 * W)` (where `n1` is word count and `W` is max word length), which is bounded by `O(L1)`. Thus, the overall complexity is dominated by the string splitting. · **Space:** O(L1 + L2), where L1 and L2 are the lengths of the input sentences. This space is used to store the word arrays.
**Pros:** Highly efficient with a single pass from both ends of the arrays.; Optimal time and space complexity for this problem.; The logic is clean and avoids redundant computations.
**Cons:** The logic with two pointers and careful indexing might be slightly less intuitive at first glance compared to the brute-force method.
### Explanation
Similar to the first approach, we begin by splitting the sentences into word arrays and ensuring `words1` is the shorter one. Instead of iterating through all split points, we can find the single required split point greedily. The core observation is that any valid arrangement must consist of a common prefix and a common suffix.

We use a pointer `i` starting from the beginning of both arrays to find the length of the longest common prefix. We advance `i` as long as `words1[i]` equals `words2[i]`.

Then, we use another pointer `j` starting from the end of both arrays to find the length of the longest common suffix. We advance `j` as long as the words at the end match. Crucially, we only consider the parts of the sentences not already part of the common prefix.

Finally, if the total length of the common prefix (`i`) and the common suffix (`j`) is equal to the total number of words in the shorter sentence (`n1`), it means every word in the shorter sentence has been matched. This confirms the sentences are similar.

```java
class Solution {
    public boolean areSentencesSimilar(String sentence1, String sentence2) {
        String[] words1 = sentence1.split(" ");
        String[] words2 = sentence2.split(" ");

        if (words1.length > words2.length) {
            return areSentencesSimilar(sentence2, sentence1);
        }

        int n1 = words1.length;
        int n2 = words2.length;

        int i = 0; // length of common prefix
        while (i < n1 && words1[i].equals(words2[i])) {
            i++;
        }

        int j = 0; // length of common suffix
        // We only check the part of words1 not covered by the prefix
        while (j < n1 - i && words1[n1 - 1 - j].equals(words2[n2 - 1 - j])) {
            j++;
        }

        // If the length of the common prefix and suffix equals the length of the shorter sentence
        return i + j == n1;
    }
}
```
### Algorithm
*   Split `sentence1` and `sentence2` into word arrays, `words1` and `words2`.
*   If `words1` is longer than `words2`, make a recursive call with swapped arguments to ensure `words1` is always the shorter array. Let `n1` be the length of `words1` and `n2` be the length of `words2`.
*   Initialize a pointer `i = 0`. Increment `i` while `i < n1` and `words1[i]` equals `words2[i]`. After this loop, `i` holds the length of the common prefix.
*   Initialize a pointer `j = 0`. Increment `j` while `j < n1 - i` and `words1[n1 - 1 - j]` equals `words2[n2 - 1 - j]`. This finds the length of the common suffix, considering only the parts of the arrays not matched by the prefix.
*   The sentences are similar if and only if the sum of the lengths of the common prefix and suffix equals the length of the shorter sentence. Return the result of `i + j == n1`.

# Solutions
### Java

```java
class Solution { public boolean areSentencesSimilar ( String sentence1 , String sentence2 ) { var words1 = sentence1 . split ( " " ); var words2 = sentence2 . split ( " " ); if ( words1 . length < words2 . length ) { var t = words1 ; words1 = words2 ; words2 = t ; } int m = words1 . length , n = words2 . length ; int i = 0 , j = 0 ; while ( i < n && words1 [ i ]. equals ( words2 [ i ])) { ++ i ; } while ( j < n && words1 [ m - 1 - j ]. equals ( words2 [ n - 1 - j ])) { ++ j ; } return i + j >= n ; } }
```

### JavaScript

```javascript
function areSentencesSimilar ( sentence1 , sentence2 ) { const [ words1 , words2 ] = [ sentence1 . split ( ' ' ), sentence2 . split ( ' ' )]; const [ m , n ] = [ words1 . length , words2 . length ]; if ( m > n ) return areSentencesSimilar ( sentence2 , sentence1 ); let [ l , r ] = [ 0 , 0 ]; for ( let i = 0 ; i < n ; i ++ ) { if ( l === i && words1 [ i ] === words2 [ i ]) l ++ ; if ( r === i && words2 [ n - i - 1 ] === words1 [ m - r - 1 ]) r ++ ; } return l + r >= m ; }
```

### CPP

```cpp
class Solution {
public:
  bool areSentencesSimilar(string sentence1, string sentence2) {
    auto words1 = split(sentence1, ' ');
    auto words2 = split(sentence2, ' ');
    if (words1.size() < words2.size()) {
      swap(words1, words2);
    }
    int m = words1.size(), n = words2.size();
    int i = 0, j = 0;
    while (i < n && words1[i] == words2[i]) {
      ++i;
    }
    while (j < n && words1[m - 1 - j] == words2[n - 1 - j]) {
      ++j;
    }
    return i + j >= n;
  }
  vector<string> split(string &s, char delim) {
    stringstream ss(s);
    string item;
    vector<string> res;
    while (getline(ss, item, delim)) {
      res.emplace_back(item);
    }
    return res;
  }
};

```

### Python

```python
class Solution : def areSentencesSimilar ( self , sentence1 : str , sentence2 : str ) -> bool : words1 , words2 = sentence1 . split (), sentence2 . split () m , n = len ( words1 ), len ( words2 ) if m < n : words1 , words2 = words2 , words1 m , n = n , m i = j = 0 while i < n and words1 [ i ] == words2 [ i ]: i += 1 while j < n and words1 [ m - 1 - j ] == words2 [ n - 1 - j ]: j += 1 return i + j >= n
```