1. subject

Given a string ( s ) And a character pattern ( p ) , Implement a support ‘?’ and ‘*’ The wildcard matches .

‘?’ It can match any single character .
‘*’ Can match any string （ Include empty string ）.
Only when two strings match exactly can the match be successful .

explain ：
s May is empty , And contains only from a-z Lowercase letters of .
p May is empty , And contains only from a-z Lowercase letters of , As well as the character ? and *.

Example 1：

 Input :
s = "aa"
p = "a"
 Output : false
 explain : "a"  Can't match  "aa"  Whole string .

Example 2：

 Input :
s = "aa"
p = "*"
 Output : true
 explain : '*'  Can match any string .

Example 3：

 Input :
s = "cb"
p = "?a"
 Output : false
 explain : '?'  Can match  'c',  But the second one  'a'  Can't match  'b'.

Example 4：

 Input :
s = "adceb"
p = "*a*b"
 Output : true
 explain :  first  '*'  Can match an empty string ,  the second  '*'  Can match string  "dce".

Example 5：

 Input :
s = "acdcb"
p = "a*c?b"
 Output : false

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/wildcard-matching

2. Ideas

（1） Dynamic programming
Train of thought reference Official solution to this problem .

3. Code implementation （Java）

// Ideas 1———— Dynamic programming 
class Solution {
    
    public boolean isMatch(String s, String p) {
    
        int m = s.length();
        int n = p.length();
        //dp[i][j]  Representation string  s  Before  i  Characters and patterns  p  Before  j  Can characters match 
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 1; i <= n; i++) {
    
            if (p.charAt(i - 1) == '*') {
    
                dp[0][i] = true;
            } else {
    
                break;
            }
        }
        for (int i = 1; i <= m; i++) {
    
            for (int j = 1; j <= n; j++) {
    
                if (p.charAt(j - 1) == '*') {
    
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                } else if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)) {
    
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }
}