-
Notifications
You must be signed in to change notification settings - Fork 1
/
0044.py
31 lines (25 loc) · 837 Bytes
/
0044.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
def isMatch(self, s: str, p: str) -> bool:
@cache
def match(posS, posP):
if posS == len(s) and posP == len(p):
return True
if posP == len(p):
return False
# wildcards
if p[posP] == "?":
if posS == len(s):
return False
return match(posS + 1, posP + 1)
if p[posP] == "*":
for i in range(posS, len(s) + 1):
if match(i, posP + 1):
return True
return False
if posS == len(s):
return False
# same letters
if p[posP] == s[posS]:
return match(posS + 1, posP + 1)
return False
return match(0, 0)