Wildcard Matching

• Define a recursive function isMatch(s_idx, p_idx) that checks if s from index s_idx matches p from index p_idx.
• Base Case 1: If the pattern pointer p_idx reaches the end, the match is successful only if the string pointer s_idx has also reached the end.
• Base Case 2: If the string pointer s_idx reaches the end, the remainder of the pattern must consist solely of * characters to match an empty string.
• Recursive Step for *: If the current pattern character p[p_idx] is *, there are two possibilities:
  1. The * matches an empty sequence. We move to the next character in the pattern: isMatch(s_idx, p_idx + 1).
  2. The * matches one or more characters. We consume a character from the string and stay at the same * in the pattern: isMatch(s_idx + 1, p_idx). The result is true if either path succeeds.
• Recursive Step for ? or matching characters: If p[p_idx] is ? or equals s[s_idx], we advance both pointers: isMatch(s_idx + 1, p_idx + 1).
• Mismatch: If none of the above, it's a mismatch, return false.

The core idea is to define a helper function, say solve(i, j), which returns true if the substring s[i:] matches the sub-pattern p[j:]. The logic proceeds by comparing characters at s[i] and p[j].

• If p[j] is a normal character, it must match s[i]. If they match, we recurse on solve(i+1, j+1).
• If p[j] is ?, it matches any character, so we recurse on solve(i+1, j+1).
• If p[j] is *, it creates a choice. The * can match nothing, so we check solve(i, j+1). Or, it can match the character s[i] (and possibly more), so we check solve(i+1, j). If either of these recursive calls returns true, then we have a match.

This method is simple to conceptualize but suffers from massive performance issues due to overlapping subproblems, where the function recalculates solve(i, j) for the same i and j multiple times.

1class Solution {2    public boolean isMatch(String s, String p) {3        return solve(s, p, 0, 0);4    }5 6    private boolean solve(String s, String p, int i, int j) {7        // If pattern is exhausted, string must also be exhausted for a match.8        if (j == p.length()) {9            return i == s.length();10        }11 12        char pChar = p.charAt(j);13 14        if (pChar == '*') {15            // Option 1: '*' matches empty sequence. Move to next pattern char.16            if (solve(s, p, i, j + 1)) {17                return true;18            }19            // Option 2: '*' matches current string char. Move to next string char.20            // This is only possible if string is not exhausted.21            if (i < s.length() && solve(s, p, i + 1, j)) {22                return true;23            }24        } else {25            // Check for a match of the current characters.26            boolean firstMatch = (i < s.length()) && (pChar == '?' || pChar == s.charAt(i));27            if (firstMatch && solve(s, p, i + 1, j + 1)) {28                return true;29            }30        }31 32        return false;33    }34}

• The recursive structure is the same as the pure recursive approach.
• A 2D array, memo[s.length() + 1][p.length() + 1], is used to store the results of subproblems.
• Initialize the memo table with a value indicating 'not computed' (e.g., null).
• In the recursive function solve(i, j), first check if memo[i][j] has been computed. If yes, return the stored value.
• If not, compute the result using the same recursive logic as before.
• Before returning the computed result, store it in memo[i][j] for future use.

We augment the recursive solution with a 2D array, memo, to store the outcomes of solve(i, j). The state (i, j) represents the subproblem of matching s.substring(i) with p.substring(j). We can use a Boolean[][] array, where null signifies an uncomputed state.

The logic of the recursive function remains identical, but with two key additions:

1. Check Memo: At the beginning of the function, check if (memo[i][j] != null). If it's not null, we've solved this subproblem before, so we return the stored result memo[i][j].
2. Save to Memo: After computing the result ans for the state (i, j), we store it before returning: memo[i][j] = ans.

This ensures that each subproblem (i, j) is solved exactly once.

1class Solution {2    private Boolean[][] memo;3    private String s;4    private String p;5 6    public boolean isMatch(String s, String p) {7        this.s = s;8        this.p = p;9        this.memo = new Boolean[s.length() + 1][p.length() + 1];10        return solve(0, 0);11    }12 13    private boolean solve(int i, int j) {14        if (memo[i][j] != null) {15            return memo[i][j];16        }17 18        boolean ans;19        if (j == p.length()) {20            ans = (i == s.length());21        } else {22            char pChar = p.charAt(j);23            if (pChar == '*') {24                // '*' matches empty OR '*' matches one char from s25                ans = solve(i, j + 1) || (i < s.length() && solve(i + 1, j));26            } else {27                boolean firstMatch = (i < s.length()) && (pChar == '?' || pChar == s.charAt(i));28                ans = firstMatch && solve(i + 1, j + 1);29            }30        }31        32        return memo[i][j] = ans;33    }34}

• Create a 2D boolean array dp of size (s.length + 1) x (p.length + 1).
• dp[i][j] will be true if the first i characters of s match the first j characters of p.
• Initialization:
  • dp[0][0] = true (empty string matches empty pattern).
  • For the first row (i=0), dp[0][j] is true if p[j-1] is * and dp[0][j-1] was true. This handles patterns like *, a*, ** matching an empty string.
• Transitions: Iterate from i = 1 to s.length and j = 1 to p.length:
  • If p[j-1] is ? or p[j-1] == s[i-1], the match depends on the previous substrings: dp[i][j] = dp[i-1][j-1].
  • If p[j-1] is *, it can either match an empty sequence (look at dp[i][j-1]) or match the current character s[i-1] (look at dp[i-1][j]). So, dp[i][j] = dp[i][j-1] || dp[i-1][j].
  • Otherwise, dp[i][j] = false.
• Result: The final answer is dp[s.length][p.length].

We construct a DP table dp of size (m+1) x (n+1), where m is the length of s and n is the length of p. The entry dp[i][j] holds the boolean result for s.substring(0, i) and p.substring(0, j).

The table is filled based on the following rules:

1. dp[0][0] = true: An empty string matches an empty pattern.
2. dp[0][j] (first row): An empty string s can only be matched by a pattern p if the pattern consists of *s. So, dp[0][j] is true if p[j-1] is * and the pattern up to j-1 also matched an empty string (dp[0][j-1]).
3. For i > 0 and j > 0:
   • If p[j-1] is a letter that matches s[i-1], or if p[j-1] is ?, then the current characters match. The result depends entirely on whether the prefixes before these characters matched: dp[i][j] = dp[i-1][j-1].
   • If p[j-1] is *, it can either be ignored (matching an empty sequence), in which case the result is dp[i][j-1], or it can match s[i-1], in which case the result depends on dp[i-1][j]. Thus, dp[i][j] = dp[i][j-1] || dp[i-1][j].

The final answer is located at dp[m][n].

1class Solution {2    public boolean isMatch(String s, String p) {3        int m = s.length();4        int n = p.length();5        boolean[][] dp = new boolean[m + 1][n + 1];6 7        dp[0][0] = true;8 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) == '*') {18                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];19                } else if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)) {20                    dp[i][j] = dp[i - 1][j - 1];21                }22            }23        }24 25        return dp[m][n];26    }27}

• Use two pointers for the string (sPtr) and pattern (pPtr).
• Use two additional variables to handle *: starIdx to store the position of the last * in the pattern, and sMatchIdx to store the position in the string that was matched up to that *.
• Iterate through the string s with sPtr:
  1. If p[pPtr] matches s[sPtr] (or is ?), advance both sPtr and pPtr.
  2. If p[pPtr] is *, save its position in starIdx and the current sPtr in sMatchIdx. Then, advance only pPtr, effectively treating * as matching an empty sequence for now.
  3. If a mismatch occurs and a * has been seen before (starIdx != -1), backtrack. Move pPtr to starIdx + 1, and advance sMatchIdx. Then, set sPtr = sMatchIdx. This makes the * consume one more character from the string.
  4. If a mismatch occurs and no * has been seen, a match is impossible. Return false.
• After the loop: Once sPtr has traversed the entire string, any remaining characters in the pattern must be *s. Advance pPtr past any trailing *s.
• Result: The match is successful if pPtr has reached the end of the pattern.

This method cleverly uses a constant amount of extra space by keeping track of the last seen * character in the pattern. This * serves as a fallback point.

We iterate through the string s with a pointer sPtr.

• If the characters at sPtr and pPtr match (or p[pPtr] is ?), we advance both pointers.
• If p[pPtr] is *, we record its position (starIdx) and the current string position (sMatchIdx). We then advance pPtr but not sPtr, greedily assuming the * matches an empty string.
• If we encounter a mismatch and p[pPtr] is not *, we check if we have a starIdx to fall back on. If we do, it means our previous greedy assumption about the * was wrong. We must backtrack: we reset pPtr to the position after the star (starIdx + 1) and set sPtr to sMatchIdx + 1. We also increment sMatchIdx itself, so the next time we backtrack to this same star, it will match an even longer sequence.
• If we mismatch and have no starIdx to backtrack to, the match fails.

After the string s is fully traversed, any remaining characters in p must be * for a valid match.

1class Solution {2    public boolean isMatch(String s, String p) {3        int sPtr = 0, pPtr = 0;4        int starIdx = -1, sMatchIdx = 0;5 6        while (sPtr < s.length()) {7            // Case 1: Characters match or pattern has '?'8            if (pPtr < p.length() && (p.charAt(pPtr) == '?' || p.charAt(pPtr) == s.charAt(sPtr))) {9                sPtr++;10                pPtr++;11            } 12            // Case 2: Pattern has '*'13            else if (pPtr < p.length() && p.charAt(pPtr) == '*') {14                starIdx = pPtr;15                sMatchIdx = sPtr;16                pPtr++;17            } 18            // Case 3: Mismatch, but we can backtrack to a '*'19            else if (starIdx != -1) {20                pPtr = starIdx + 1;21                sMatchIdx++;22                sPtr = sMatchIdx;23            } 24            // Case 4: Mismatch and no '*' to backtrack to25            else {26                return false;27            }28        }29 30        // Check for remaining characters in pattern (must be '*')31        while (pPtr < p.length() && p.charAt(pPtr) == '*') {32            pPtr++;33        }34 35        return pPtr == p.length();36    }37}