Wildcard Pattern Matching

'''
Logic:
we will traverse the string from backside.
->There is three case possible here:
i)pattern and string current character matches,so match for rest string ie. n-1,m-1
ii)pattern current character is '?',which is equivalent to any one character,
   same as case 1 so so match for rest string. ie. n-1,m-1
iii)pattern current character is '*',so either * can be empty character or
    some character.
    a)empty character:so character index will be decreased.
    b)some character:so decrease string index only,so pattern index is still
      pointing to same '*',so same both condition arises again.In this
      way,all 3 cases,no character,one character and some character will
      be covered.

Few base case:
1.both string and pattern got over
2.string got over but pattern contains only *
3.string is remaining but pattern got over so False
'''
def fun(s, p, n, m, dp):
    # both finished
    if n < 0 and m < 0:
        return True

    # pattern finished but string left
    if m < 0:
        return False

    # string finished but pattern left
    if n < 0:
        while m >= 0 and p[m] == '*':
            m -= 1
        return m < 0

    # memo check
    if dp[n][m] != -1:
        return dp[n][m]

    # normal match or '?'
    if s[n] == p[m] or p[m] == '?':
        dp[n][m] = fun(s, p, n-1, m-1, dp)
        return dp[n][m]

    # '*'
    if p[m] == '*':
        dp[n][m] = fun(s, p, n-1, m, dp) or fun(s, p, n, m-1, dp)
        return dp[n][m]

    # mismatch
    dp[n][m] = False
    return False


class Solution:
    def isMatch(self, s: str, pat: str) -> bool:

        n = len(s)
        m = len(pat)

        dp = [[-1 for _ in range(m)] for _ in range(n)]

        return fun(s, pat, n-1, m-1, dp)