Wildcard Matching

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:

  • '?' Matches any single character.
  • '*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

 

Example 1:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input: s = "aa", p = "*"
Output: true
Explanation: '*' matches any sequence.

Example 3:

Input: s = "cb", p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

 

Constraints:

  • 0 <= s.length, p.length <= 2000
  • s contains only lowercase English letters.
  • p contains only lowercase English letters, '?' or '*'.
SOLUTION:
class Solution:
    def isSame(self, a, b):
        if a == "?" or b == "?":
            return True
        return a == b
    
    def isMatchRec(self, s, p, i, j, m, n):
        if j >= n:
            return i >= m
        if i >= m:
            if j >= n:
                return True
        if (i, j) in self.cache:
            return self.cache[(i, j)]
        if i >= m:    
            res = p[j] == "*" and self.isMatchRec(s, p, i, j + 1, m, n)
            self.cache[(i, j)] = res
            return res
        if p[j] == "*":
            res = self.isMatchRec(s, p, i, j + 1, m, n) or self.isMatchRec(s, p, i + 1, j, m, n)
            self.cache[(i, j)] = res
            return res
        res = self.isSame(s[i], p[j]) and self.isMatchRec(s, p, i + 1, j + 1, m, n)
        self.cache[(i, j)] = res
        return res
    
    def isMatch(self, s: str, p: str) -> bool:
        m = len(s)
        n = len(p)
        self.cache = {}
        return self.isMatchRec(s, p, 0, 0, m, n)

Comments

Post a Comment

Popular posts from this blog

Minimum Number of Operations to Move All Balls to Each Box

You have n boxes. You are given a binary string boxes of length n , where boxes[i] is '0' if the i th box is empty , and '1' if it contains one ball. In one operation, you can move one ball from a box to an adjacent box. Box i is adjacent to box j if abs(i - j) == 1 . Note that after doing so, there may be more than one ball in some boxes. Return an array answer of size n , where answer[i] is the minimum number of operations needed to move all the balls to the i th box. Each answer[i] is calculated considering the initial state of the boxes.   Example 1: Input: boxes = "110" Output: [1,1,3] Explanation: The answer for each box is as follows: 1) First box: you will have to move one ball from the second box to the first box in one operation. 2) Second box: you will have to move one ball from the first box to the second box in one operation. 3) Third box: you will have to move one ball from the first box to the third box in two...
Read more

Efficient Generation of Nth Row of Binomial Coefficient Modulo M

Efficient Generation of Nth Row of Binomial Coefficient Modulo M Efficient Generation of Nth Row of Binomial Coefficient Modulo M Introduction Calculating the binomial coefficient (also known as the combinatorial coefficient) is a common task in mathematics and programming. However, when the modulo M is not prime, finding an efficient method becomes more challenging. In this article, we will explore a technique that allows us to efficiently generate the Nth row of the binomial coefficient modulo M, even when M is not necessarily prime. This technique utilizes prime factorization and a sieve algorithm to achieve efficient computation. The Implementation Let's take a look at the implementation of the technique: from collections import Counter N = 1 + 10 ** 6 v = [False] * N spf = [1] * N for i in range(2, N, 2): spf[i] = 2 for i in range(3, N, 2): if not v[i]: spf[i] = i j = i while j * i 1: ctr[spf[a]...
Read more

Lazy Deletion in Heap: A Wrapper for Python heapq

Lazy Deletion in Heap: A Wrapper for Python heapq Lazy Deletion in Heap: A Wrapper for Python heapq In many programming scenarios, we often encounter situations where we need to maintain a heap data structure and perform operations such as insertion, deletion, and retrieval of the minimum element efficiently. Python provides a built-in module called heapq that offers heap operations. However, the standard heapq module does not provide direct support for lazy deletion, which can be useful in certain cases. In this article, we will explore a wrapper class, Heap , that extends the functionality of the Python heapq library to support lazy deletion in a heap. The Heap Class The Heap class is a wrapper that encapsulates the heapq module to enable lazy deletion in a heap. Let's go through its main methods and their functionalities: __init__(self) : Initializes the Heap instance by creating an empty heap and a defaultdict to track the deleted elements ...
Read more