How hard is LeetCode 1813. Sentence Similarity III?

LeetCode 1813. Sentence Similarity III is rated Medium on LeetCode.

What is the time complexity of LeetCode 1813. Sentence Similarity III?

The Python solution on this page runs in O(L).

What is the space complexity of LeetCode 1813. Sentence Similarity III?

The Python solution on this page uses O(L), where L is the sum of the lengths of the two sentences auxiliary space.

What topics does LeetCode 1813. Sentence Similarity III cover?

LeetCode 1813. Sentence Similarity III is tagged Array, Two Pointers and String on LeetCode.

Sentence Similarity III — LeetCode 1813 Python Solution

MediumArrayTwo PointersString

Problem: #1813
Pattern: Two Pointers
Reading time: 2 min
Source: leetcode.com

The 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.

Python solution

Python

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

Complexity

Measure	Complexity
Time	O(L)
Space	O(L), where L is the sum of the lengths of the two sentences auxiliary

Pattern: Two Pointers

Use the order already in the input to discard half the search space at every step. LeetCode 1813. Sentence Similarity III is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Two Pointers.

The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1813. Sentence Similarity III?: LeetCode 1813. Sentence Similarity III is rated Medium on LeetCode.
What is the time complexity of LeetCode 1813. Sentence Similarity III?: The Python solution on this page runs in O(L).
What is the space complexity of LeetCode 1813. Sentence Similarity III?: The Python solution on this page uses O(L), where L is the sum of the lengths of the two sentences auxiliary space.
What topics does LeetCode 1813. Sentence Similarity III cover?: LeetCode 1813. Sentence Similarity III is tagged Array, Two Pointers and String on LeetCode.