Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1813.html
1813. Sentence Similarity III
Level
Medium
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.
Example 4:
Input: sentence1 = “Luky”, sentence2 = “Lucccky”
Output: false
Constraints:
1 <= sentence1.length, sentence2.length <= 100sentence1andsentence2consist of lowercase and uppercase English letters and spaces.- The words in
sentence1andsentence2are separated by a single space.
Solution
If sentence1 and sentence2 are equal, return true. Otherwise, split sentence1 and sentence2 into two arrays by spaces.
If the two arrays have the same length, then return true if and only if the two arrays are exactly the same.
If the two arrays have different lengths, then check whether it is possible to obtain the longer array by inserting a consecutive part into the shorter array. If so, return true. Otherwise, return false.
-
class Solution { public boolean areSentencesSimilar(String sentence1, String sentence2) { if (sentence1.equals(sentence2)) return true; String[] array1 = sentence1.split(" "); String[] array2 = sentence2.split(" "); int length1 = array1.length, length2 = array2.length; if (length1 == length2) { for (int i = 0; i < length1; i++) { if (!array1[i].equals(array2[i])) return false; } return true; } else if (length1 < length2) return areSentencesSimilar(array1, array2); else return areSentencesSimilar(array2, array1); } public boolean areSentencesSimilar(String[] array1, String[] array2) { int length1 = array1.length, length2 = array2.length; int difference = length2 - length1; int[] indices = new int[length1]; for (int i = 0; i < length1; i++) indices[i] = i + difference; for (int i = 0; i <= length1; i++) { boolean flag = true; for (int j = 0; j < length1; j++) { int index = indices[j]; if (!array1[j].equals(array2[index])) { flag = false; break; } } if (flag) return true; if (i < length1) indices[i] -= difference; } return false; } } ############ 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; } } -
// OJ: https://leetcode.com/problems/sentence-similarity-iii/ // Time: O(N) // Space: O(N) class Solution { deque<string> split(string &s) { istringstream ss(s); string word; deque<string> ans; while (ss >> word) ans.push_back(word); return ans; } public: bool areSentencesSimilar(string a, string b) { if (a == b) return true; if (a.size() < b.size()) swap(a, b); auto A = split(a), B = split(b); while (B.size() && A.front() == B.front()) A.pop_front(), B.pop_front(); while (B.size() && A.back() == B.back()) A.pop_back(), B.pop_back(); return B.empty(); } }; -
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 ############ # 1813. Sentence Similarity III # https://leetcode.com/problems/sentence-similarity-iii class Solution: def areSentencesSimilar(self, s1: str, s2: str) -> bool: s1 = s1.split() s2 = s2.split() def good(a, b): a = collections.deque(a) b = collections.deque(b) while len(a) > 0 and len(b) > 0 and a[0] == b[0]: a.popleft() b.popleft() while len(a) > 0 and len(b) > 0 and a[-1] == b[-1]: a.pop() b.pop() return len(a) == 0 return good(s1, s2) or good(s2, s1) def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool: s1, s2 = sentence1.split(), sentence2.split() n1, n2 = len(s1), len(s2) if n1 > n2: return self.areSentencesSimilar(sentence2, sentence1) i = 0 while i < n1 and s1[i] == s2[i]: i += 1 while i < n1 and s1[i] == s2[n2 - n1 + i]: i += 1 return i == n1 -
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 = sentence1.split(' '); const words2 = sentence2.split(' '); if (words1.length < words2.length) { return areSentencesSimilar(sentence2, sentence1); } const [m, n] = [words1.length, words2.length]; let [i, j] = [0, 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; }