Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.
'?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence). The matching should cover the entire input string (not partial).
Note:
s could be empty and contains only lowercase letters a-z. p could be empty and contains only lowercase letters a-z, and characters like ? or *. Example 1:
Input: s = "aa" p = "a" Output: false Explanation: "a" does not match the entire string "aa". Example 2:
Input: s = "aa" p = "" Output: true Explanation: '' matches any sequence. Example 3:
Input: s = "cb" p = "?a" Output: false Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'. Example 4:
Input: s = "adceb" p = "ab" Output: true Explanation: The first '' matches the empty sequence, while the second '' matches the substring "dce". Example 5:
Input: s = "acdcb" p = "a*c?b" Output: false
My code:
import numpy as np
class Solution:
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
if len(s)>0:
self.record=np.zeros([len(s),len(p)])-1
#flag=False
flag=self.judge_match(s,0,p,0)
else:
if len(p)>0:
for i in range(len(p)):
if p[i]!='*':
return False
return True
else:
return True
return bool(flag)
def judge_match(self,s,i,p,j):
if i==len(s) and j==len(p):
return 1
elif j==len(p):
return 0
if i<len(s) and self.record[i,j]!=-1:
return int(self.record[i,j])
if i<len(s) and s[i]==p[j]:
if i<len(s) and j<len(p):
self.record[i,j]=self.judge_match(s,i+1,p,j+1)
tmp=self.record[i,j]
else:
tmp=self.judge_match(s,i+1,p,j+1)
return tmp
if p[j]=='?':
if i<len(s) and j<len(p):
self.record[i,j]=self.judge_match(s,i+1,p,j+1)
tmp=self.record[i,j]
else:
tmp=self.judge_match(s,i+1,p,j+1)
return tmp
if p[j]=='*':
for start in range(i,len(s)+1):
flag1=self.judge_match(s,start,p,j+1)
if flag1:
if i<len(s) and j<len(s):
self.record[i,j]=1
return 1
if i<len(s) and j<len(p):
self.record[i,j]=0
return 0
if i<len(s) and j<len(p):
self.record[i,j]=0
return 0