44. Wildcard Matching

Dynamic Programming

class Solution {
    public boolean isMatch(String s, String p) {
        int n = s.length();
        int m = p.length();
        boolean[][] dp = new boolean[n + 1][m + 1];

        // 1. initilize base
        dp[0][0] = true;

        // 2. when s is empty
        // only "*" matches
        for (int j = 1; j <= m; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 1];
            }
        }

        // 3. fill the dp table
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                char sChar = s.charAt(i - 1);
                char pChar = p.charAt(j - 1);

                if (pChar == '?') {
                    // '?' matches any single char in s
                    // so it depends on whether i-1 and j-1 match
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (pChar == '*') {
                    // '*' has two matching modes:
                    // 0 chars, depends on the last [i][j-1]
                    // 1 or more, '*' matchs sChar, and continues to match the next cahr in s
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                } else {
                    // normal char
                    // matches when two chars are same and the previous ones matches
                    dp[i][j] = (sChar == pChar) && dp[i - 1][j - 1];
                }
            }
        }

        return dp[n][m];

    }
}

Remarks:

1. TC: $O(m\times n)$; SC: $O(m\times n)$.
2. Very similar to 10. Regular Expression Matching

Greedy

class Solution {
    public static boolean isMatch(String s, String p) {
        int i = 0;  // Pointer for string s
        int j = 0;  // Pointer for pattern p
        int n = s.length();
        int m = p.length();

        // Base case: both strings empty
        if (n == 0 && m == 0) {
            return true;
        }

        int laststar = -1;    // Position of last '*'
        int lastmatch = 0;    // Position in s where last '*' tried to match

        // Traverse the string s
        while (i < n) {
            // Case 1: Exact match or '?'
            if (j < m && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '?')) {
                i++;
                j++;
            }
            // Case 2: Pattern has '*'
            else if (j < m && p.charAt(j) == '*') {
                laststar = j;         // Remember star position
                lastmatch = i;        // Remember match position in s
                j++;                  // Move pattern forward
            }
            // Case 3: Mismatch but we saw a previous '*'
            else if (laststar != -1) {
                j = laststar + 1;     // Reset j to just after '*'
                lastmatch++;          // Try to match one more char with '*'
                i = lastmatch;        // Move i accordingly
            }
            // Case 4: Mismatch and no previous '*'
            else {
                return false;
            }
        }

        // If remaining pattern has stars, skip them
        while (j < m && p.charAt(j) == '*') {
            j++;
        }

        // If we reached the end of pattern, it's a match
        return j == m;
    }
}