| 7 | # METHOD 1 -> Recursion plus Memoization |
| 8 | |
| 9 | class Solution: |
| 10 | def helper(self, s, p, idx_s, idx_p,cache): |
| 11 | if (idx_s,idx_p) in cache: |
| 12 | return cache[(idx_s,idx_p)] |
| 13 | |
| 14 | # if we reach end of both the strings return True |
| 15 | if idx_p == len(p) and idx_s == len(s): |
| 16 | return True |
| 17 | |
| 18 | # if we reach the end of p but not s then return False |
| 19 | if idx_p == len(p): |
| 20 | return False |
| 21 | |
| 22 | # if we reach the end of s but not p then check if the remaining characters in p are * or not |
| 23 | elif idx_s == len(s): |
| 24 | res = ( p[idx_p] == '*' and self.helper(s,p,idx_s,idx_p+1,cache) ) |
| 25 | |
| 26 | # if the current characters of p and s are either equal or char of p is '?' then continue for other characters |
| 27 | elif s[idx_s] == p[idx_p] or p[idx_p] == "?": |
| 28 | res = self.helper(s,p,idx_s+1,idx_p+1,cache) |
| 29 | |
| 30 | # if the current character of p is '*' then either we include it or we leave it |
| 31 | elif p[idx_p] == '*': |
| 32 | res = self.helper(s,p,idx_s+1,idx_p,cache) or self.helper(s,p,idx_s,idx_p+1,cache) |
| 33 | # no char match |
| 34 | else: |
| 35 | return False |
| 36 | cache[(idx_s, idx_p)] = res |
| 37 | return res |
| 38 | |
| 39 | def isMatch(self, s: str, p: str) -> bool: |
| 40 | return self.helper(s,p,0,0,{}) |
| 41 | |
| 42 | |
| 43 | #METHOD 2 -> Tabulation |
nothing calls this directly
no outgoing calls
no test coverage detected