# Wildcard Matching

## Problem

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:
p = "*a*b"
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


## Solution

### 函数递归调用

 1 2  isMatch(s,p)=isMatch(s,p[1:]) or isMatch(s[1:],p) if p[0]=='*' else p[0] in (s[0],'?') and isMatch(s[1:],p[1:]) 

### DP

  1 2 3 4 5 6 7 8 9 10 11 12  if p[i-1]=='*': dp[i][0]=dp[i-1][0]#能否匹配空字符串取决于前面的pattern for j in range(1,len(s)+1): dp[i][j]=dp[i-1][j] or dp[i][j-1] or dp[i-1][j-1] elif p[i]=='?': dp[i][0]=False for j in range(1,len(s)+1): dp[i][j]=dp[i-1][j-1] else: dp[i][0]=False for j in range(1,len(s)+1): dp[i][j]=s[j-1]==p[i-1] and dp[i-1][j-1]