44. 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).

My Answer 1: Time Limit Exceeded (1616 / 1811 test cases passed.)

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        if not p:
            return not s
        
        # s 가 빈 문자열인지 아닌지 & p[0] 가 s[0] or * or ? 인지 확인 => T/F
        first_match = bool(s) and p[0] in {s[0], '*', '?'}
        
        if p[0] == '*':
            return (self.isMatch(s, p[1:]) or
                    first_match and self.isMatch(s[1:], p))
        else:
            return first_match and self.isMatch(s[1:], p[1:])

10. Regular Expression Matching 문제를 살짝 바꿔봤는데 타임리밋...

DP

Solution 1: Runtime: 936 ms - 37.53% / Memory Usage: 22.3 MB - 70.86%

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        ## RC ##
        ## APPROACH : DP ##
        ## Similar to Leetcode : 10 Regular Expression Matching ##
        ## TIME COMPLEXICITY : O(MN) ##
        ## SPACE COMPLEXICITY : O(MN) ##
        
        dp = [ [ False ] * (len(s)+1) for i in range(len(p)+1)]
        dp[0][0] = True
        # ONLY CHANGE # case 1 : s = "aa", p = "*" ==> (1,0) should be True
        for i in range(1,len(dp)):
            if p[i-1] == '*':
                dp[i][0] = dp[i-1][0]
                
        for i in range(1, len(dp)):
            for j in range(1, len(dp[0])):
                # 한 글자만 같으니까 dp[i-1][j-1]
                if( p[i-1] == s[j-1] or p[i-1] == "?"):
                    dp[i][j] = dp[i-1][j-1] 
                if( p[i-1] == "*" ):
                    # case 1 : extension, check upside and left side also
                    dp[i][j] = dp[i-1][j] or dp[i][j-1]
        return dp[-1][-1]

DP 를 만들어줘서 [0][0] 을 True 로 설정하고 계속 match 되는 부분은 계속 True 로 연결되는 듯