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的前一位置是否匹配。