1813. Sentence Similarity III

Description

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.

Solutions

Solution 1: Two Pointers

We split the two sentences into two word arrays words1 and words2 by spaces. Let the lengths of words1 and words2 be $m$ and $n$, respectively, and assume that $m \ge nn.

We use two pointers $i$ and $j$, initially $i = j = 0$. Next, we loop to check whether words1[i] is equal to words2[i], and if so, pointer $i$ continues to move right; then we loop to check whether words1[m - 1 - j] is equal to words2[n - 1 - j], and if so, pointer $j$ continues to move right.

After the loop, if $i + j \ge n$, it means that the two sentences are similar, and we return true; otherwise, we return false.

The time complexity is $O(L)$, and the space complexity is $O(L)$, where $L$ is the sum of the lengths of the two sentences.

Python3JavaC++GoTypeScriptJavaScript

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

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;
    }
}

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;
    }
};

func areSentencesSimilar(sentence1 string, sentence2 string) bool {
    words1, words2 := strings.Fields(sentence1), strings.Fields(sentence2)
    if len(words1) < len(words2) {
        words1, words2 = words2, words1
    }
    m, n := len(words1), len(words2)
    i, j := 0, 0
    for i < n && words1[i] == words2[i] {
        i++
    }
    for j < n && words1[m-1-j] == words2[n-1-j] {
        j++
    }
    return i+j >= n
}

function areSentencesSimilar(sentence1: string, sentence2: string): boolean {
    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;
}

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;
}

Comments