Wildcard Matching

1public boolean isMatch(String s, String p) {
2    int m = s.length(), n = p.length();
3    boolean[][] dp = new boolean[m + 1][n + 1];
4
5    // Base case: empty pattern matches empty string
6    dp[0][0] = true;
7
8    // Base case: pattern starting with '*' can match empty string
9    for (int j = 1; j <= n; j++) {
10        if (p.charAt(j - 1) == '*') {
11            dp[0][j] = dp[0][j - 1];
12        }
13    }
14
15    for (int i = 1; i <= m; i++) {
16        for (int j = 1; j <= n; j++) {
17            if (p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '?') {
18                dp[i][j] = dp[i - 1][j - 1];
19            } else if (p.charAt(j - 1) == '*') {
20                dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
21            }
22        }
23    }
24
25    return dp[m][n];
26}