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: Dequeue / Common Prefix + Suffix
Break sequences to words, store them in two deques. Pop the common prefix and suffix. At least one of the deque should be empty.
Time complexity: O(m+n)
Space complexity: O(m+n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua class Solution { public: bool areSentencesSimilar(string s1, string s2) { auto getWords = [](const string& s) { stringstream ss(s); deque<string> words; while (ss) { words.emplace_back(""); ss >> words.back(); } return words; }; deque<string> w1 = getWords(s1), w2 = getWords(s2); while (w1.size() && w2.size() && w1.front() == w2.front()) w1.pop_front(), w2.pop_front(); while (w1.size() && w2.size() && w1.back() == w2.back()) w1.pop_back(), w2.pop_back(); return w1.empty() || w2.empty(); } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 |
# Author: Huahua class Solution: def areSentencesSimilar(self, s1: str, s2: str) -> bool: w1 = deque(s1.split()) w2 = deque(s2.split()) while w1 and w2 and w1[0] == w2[0]: w1.popleft(), w2.popleft() while w1 and w2 and w1[-1] == w2[-1]: w1.pop(), w2.pop() return len(w1) * len(w2) == 0 |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment