[LeetCode] 44. Wildcard Matching

Problem : https://leetcode.com/problems/wildcard-matching/

This problem is similar to  10. Regular Expression Matching

It is a simple problem if we don't consider character '*'. 

When it encounters '*',  it has 2 options:

1. Use '*' to match the current character in S and keep the '*' for the next character matching
2. Skip '*' as  '*' is used to match empty sequence. Then use next character in P to match current character in S.

To avoid checking if S[i] matches P[j] repeatedly, it needs to memorize the result from previous iteration.

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        
        memo = [[0] * (len(p)+1) for _ in range(len(s)+1)]
        
        def helper(i, j):
            if j >= len(p):
                return i >= len(s)
            
            if memo[i][j] != 0:
                return memo[i][j] == 1
            
            if i < len(s) and s[i] == p[j]:
                return helper(i+1, j+1)
            
            if i < len(s) and p[j] == '?':
                return helper(i+1, j+1)
            
            if i < len(s) and p[j] == '*':
            
            	# Match S[i] with '*'
                # Move to next character of S
                # Keep '*' in P
                if helper(i+1, j):
                    memo[i][j] = 1
                    return True
            	
                # Use '*' to match empty sequence
                # Stay on the current character of S
                # Move to next character of P 
                if helper(i, j+1):
                    memo[i][j] = 1
                    return True
            
            if i == len(s) and p[j] == '*':
                return helper(i, j+1)
            
            memo[i][j] = -1
            return False
                
        return helper(0, 0)