README_EN.md

1813. Sentence Similarity III

中文文档

Description

A sentence is a list of words that are separated by a single space with no leading or trailing spaces. For example, "Hello World", "HELLO", "hello world hello world" are all sentences. Words consist of only uppercase and lowercase English letters.

Two sentences sentence1 and sentence2 are similar if it is possible to insert an arbitrary sentence (possibly empty) inside one of these sentences such that the two sentences become equal. For example, sentence1 = "Hello my name is Jane" and sentence2 = "Hello Jane" can be made equal by inserting "my name is" between "Hello" and "Jane" in sentence2.

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

Python3

class Solution:
    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:
        if sentence1 == sentence2:
            return True
        n1, n2 = len(sentence1), len(sentence2)
        if n1 == n2:
            return False
        if n1 < n2:
            sentence1, sentence2 = sentence2, sentence1
        words1, words2 = sentence1.split(), sentence2.split()
        i = j = 0
        n1, n2 = len(words1), len(words2)
        while i < n2 and words1[i] == words2[i]:
            i += 1
        if i == n2:
            return True
        while j < n2 and words1[n1 - 1 - j] == words2[n2 - 1 - j]:
            j += 1
        return j == n2 or i + j == n2

Java

class Solution {
    public boolean areSentencesSimilar(String sentence1, String sentence2) {
        if (sentence1.equals(sentence2)) {
            return true;
        }
        int n1 = sentence1.length(), n2 = sentence2.length();
        if (n1 == n2) {
            return false;
        }
        if (n1 < n2) {
            String t = sentence1;
            sentence1 = sentence2;
            sentence2 = t;
        }
        String[] words1 = sentence1.split(" ");
        String[] words2 = sentence2.split(" ");
        int i = 0, j = 0;
        n1 = words1.length;
        n2 = words2.length;
        while (i < n2 &&  words1[i].equals(words2[i])) {
            ++i;
        }
        if (i == n2) {
            return true;
        }
        while (j < n2 && words1[n1 - 1 - j].equals(words2[n2 - 1 - j])) {
            ++j;
        }
        return j == n2 || i + j == n2;
    }
}

Go

func areSentencesSimilar(sentence1 string, sentence2 string) bool {
	if sentence1 == sentence2 {
		return true
	}
	l1, l2 := len(sentence1), len(sentence2)
	if l1 == l2 {
		return false
	}
	if l1 < l2 {
		sentence1, sentence2 = sentence2, sentence1
	}
	i, j := 0, 0
	w1, w2 := strings.Fields(sentence1), strings.Fields(sentence2)
	l1, l2 = len(w1), len(w2)
	for i < l2 && w1[i] == w2[i] {
		i++
	}
	if i == l2 {
		return true
	}
	for j < l2 && w1[l1-1-j] == w2[l2-1-j] {
		j++
	}
	return j == l2 || i+j == l2
}

C++

class Solution {
public:
    bool areSentencesSimilar(string sentence1, string sentence2) {
        if (sentence1 == sentence2) return true;
        int n1 = sentence1.size(), n2 = sentence2.size();
        if (n1 == n2) return false;

        if (n1 < n2) swap(sentence1, sentence2);
        auto words1 = split(sentence1);
        auto words2 = split(sentence2);
        int i = 0, j = 0;
        n1 = words1.size(), n2 = words2.size();

        while (i < n2 && words1[i] == words2[i]) ++i;
        if (i == n2) return true;

        while (j < n2 && words1[n1 - 1 - j] == words2[n2 - 1 - j]) ++j;
        return j == n2 || i + j == n2;
    }

    vector<string> split(const string &str) {
        vector<string> words;
        int i = str.find_first_not_of(' ');
        int j = str.find_first_of(' ', i);
        while (j != string::npos) {
            words.emplace_back(str.substr(i, j - i));
            i = str.find_first_not_of(' ', j);
            j = str.find_first_of(' ', i);
        }
        words.emplace_back(str.substr(i));
        return words;
    }
};

...