Question original link https://leetcode.com/problems/wildcard-matching

The implementation supports’?’and’ * ‘wildcard pattern matching.

‘?’ matches any single character.

‘*’ matches any character sequence (including null).

You must match the entire input string (not just partial substrings).

Some examples:

isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

Dynamic programming is used. Set the input string as s, length as m, mode string as P, length as N, Boolean array DP [M + 1] [n + 1].

DP [0] [J + 1] indicates whether the empty string matches P [0.. J], and DP [i + 1] [J + 1] indicates whether s [0.. I] matches P [0.. J].

If P [J] = ‘*’, then DP [i + 1] [J + 1] = DP [i] [J + 1] | DP [i + 1] [J].

If P [J] = ‘?’ | P [J] = = s [i], then DP [i + 1] [J + 1] = DP [i] [J].

In other cases, DP [i + 1] [J + 1] = false.

public class Solution {
  public static boolean isMatch(String s, String p) {
    boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
    dp[0][0] = true;
    for (int j = 0; j < p.length(); j++) {
      if (dp[0][j] && p.charAt(j) == '*') {
        dp[0][j + 1] = true;
      }
    }
    for (int i = 0; i < s.length(); i++) {
      for (int j = 0; j < p.length(); j++) {
        if (p.charAt(j) == '*') {
          dp[i + 1][j + 1] = dp[i][j + 1] || dp[i + 1][j];
        } else if (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i)) {
          dp[i + 1][j + 1] = dp[i][j];
        }
      }
    }
    return dp[s.length()][p.length()];
  }
}