Problem Statement in English

You’re given a string s and a pattern p.

The pattern can contain the wildcard character *, which can match any substring (including an empty substring). Your task is to determine if the string s matches the pattern p.

Approach

The simplest thing you can do is to split the pattern p by the wildcard character *.

Find the first occurrence of the first part of the pattern in the string s.

Then, find the last occurrence of the last part of the pattern in the string s.

Return True if the index of the first occurrence is less than the index of the last occurrence.

Solution in Python


class Solution:
    def hasMatch(self, s: str, p: str) -> bool:
        l = p.split("*")
        len_s = len(s)
        i1, i2 = -1, len_s

        if l[0] != "":
            i1 = s.find(l[0])
            if i1 == -1:
               return False

        if l[1] != "":
            t = [i for i in range(len(s)) if s.startswith(l[1], i)]
            if not t:
                return False
            i2 = t[-1]

        return i1 + (len(l[0]) - 1) < i2

Complexity

  • Time: $O(n)$
    Since we iterate over $n$ characters in the string s to find the first and last occurrences of the parts of the pattern.

  • Space: $O(1)$
    Since we don’t use any extra space.

And we are done.