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.

Examples

Example 1:

1
2
3

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:

1
2
3

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:

1
2
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.

Solution

Method 1 - Scan shorter sentence

By identifying the longest prefix and suffix that are common between the two word lists, we can determine the parts of the sentences that could potentially be identical if additional words (a valid phrase) are inserted between them.

The validity of insertion comes down to whether the non-matching middle portions (after excluding the prefix and suffix) can logically align with an inserted sentence or not.

Here is the approach:

  1. Splitting Sentences into Words:
    • First, we split both sentences into arrays of words using space as the delimiter.
    • For example:
      • sentence1 = "My name is Haley" results in words1 = ["My", "name", "is", "Haley"]
      • sentence2 = "My Haley" results in words2 = ["My", "Haley"]
  2. Finding Common Prefix:
    • We traverse from the beginning of both word arrays, counting how many words match at corresponding positions (common prefix).
    • If words1[i] == words2[i], we increment i.
  3. Finding Common Suffix:
    • Similarly, we traverse from the end of both word arrays, counting how many words match at corresponding positions (common suffix).
    • If words1[n1 - 1 - j] == words2[n2 - 1 - j], we increment j.
  4. Checking the Condition:
    • If the sum of the lengths of the common prefix and common suffix is at least the length of the shorter sentence, then the sentences can be made similar by inserting the missing words in the middle.
    • Mathematically, the condition is: i + j >= min(n1, n2), where n1 and n2 are the lengths of words1 and words2, respectively.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


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

        int i = 0, n1 = words1.length, n2 = words2.length;
        while (i < n1 && i < n2 && words1[i].equals(words2[i])) {
            i++;
        }

        int j = 0;
        while (j < n1 && j < n2 && words1[n1 - 1 - j].equals(words2[n2 - 1 - j])) {
            j++;
        }

        return i + j >= Math.min(n1, n2);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:
        words1 = sentence1.split(" ")
        words2 = sentence2.split(" ")

        i = 0
        n1 = len(words1)
        n2 = len(words2)
        
        while i < n1 and i < n2 and words1[i] == words2[i]:
            i += 1

        j = 0
        while j < n1 and j < n2 and words1[n1 - 1 - j] == words2[n2 - 1 - j]:
            j += 1

        return i + j >= min(n1, n2)

Complexity

  • ⏰ Time complexity: O(m + n), m is the length of sentence1 and n is the length of sentence2. In the worst case, we need to compare all words in both sentences, which gives us a linear time complexity relative to the total number of words in both sentences.
  • 🧺 Space complexity: O(m + n), The space complexity is also linear in terms of the number of words split in both sentences. This mainly comes from storing the split words in arrays or lists.