dsa-problem

Wildcard Matching

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

Problem

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 ‘*’.

Test Cases

"aa"
"a"
"aa"
"*"
"cb"
"?a"
"aa"
"aaaaa"
"aa"
"aa*"
"adceb"
"*a*b"
"babaaababaabababbbbbbaabaabbabababbaababbaaabbbaaab"
"***bba**a*bbba**aab**b"

See the problem

​

Solution

Solution Recursive: Python

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        p_size = len(p)
        s_size = len(s)
        i=j=0
        while i<p_size:
            if j>=s_size:
                while (i<p_size and p[i]=="*"):
                    i+=1
                if i<p_size:
                    return False
                else:
                    return True
            elif (p[i]==s[j] or p[i]=='?'):
                i+=1
                j+=1
            elif (p[i]=="*"):
                return ( 
                    self.isMatch(s[j+1:], p[i+1:]) or 
                    self.isMatch(s[j:], p[i+1:]) or 
                    self.isMatch(s[j+1:], p[i:]))
            else:
                return False
        if j<s_size:
            return False
        else:
            return True

​

Solution Iterative: Python

class Solution:
    def get_value_at_index(self, arr, i, j):
        if i >= 0 and j >= 0:
            return arr[i % 2][j]
        elif i == -1 and j == -1:
            return True
        else:
            return False

    def isMatch(self, s: str, p: str) -> bool:
        p_size = len(p)
        s_size = len(s)
        first_el = True

        if not s_size:
            for i in range(p_size):
                if p[i] != "*":
                    return False
            return True
        if not p_size:
            return False

        mem = [[False] * s_size for i in range(2)]

        for i in range(p_size):
            for j in range(s_size):
                if p[i] == s[j] or p[i] == "?":
                    mem[i % 2][j] = first_el or self.get_value_at_index(
                        mem, i - 1, j - 1
                    )
                    first_el = False
                elif p[i] == "*":
                    mem[i % 2][j] = (
                        self.get_value_at_index(mem, i - 1, j - 1)
                        or self.get_value_at_index(mem, i, j - 1)
                        or self.get_value_at_index(mem, i - 1, j)
                    )
                else:
                    mem[i % 2][j] = False
                    first_el = False

        return mem[(p_size - 1) % 2][s_size - 1]

​