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
class Solution:
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
dp = [[False for i in range(len(p)+1)] for j in range(len(s)+1)]
dp[0][0] = True
for i in range(len(p)):
if (p[i]=='*' and dp[0][i]):
dp[0][i+1] = True
for i in range(len(s)):
for j in range(len(p)):
if s[i]==p[j] or p[j]=='?':
dp[i+1][j+1] = dp[i][j]
elif p[j]=='*':
dp[i+1][j+1] = dp[i+1][j] or dp[i][j+1]
return dp[-1][-1]
用bool型二维数组vvb[i][j]表示s的前i个字符和p的前j个字符是否匹配。
初始值，vvb[0][0]为true，vvb[0][j]的值取决于p前一个位置是否为‘*’以及前一情况是否匹配。
当p[j]等于‘?’或者s[i]等于p[j]时，则vvb[i][j]的值取决于vvb[i-1][j-1]，即为s的前一位置和p的前一位置是否匹配；
当p[j]等于‘’时，如果该‘’可以匹配s中的0个或者1个字符，分别对应vvb[i][j-1]，即s的当前位置和p的前一位置是否匹配，以及vvb[i-1][j-1]，即s的前一位置和p的前一位置是否匹配。