Wildcard Matching - Optimized [C++]
IntuitionThe problem is a pattern-matching task where * matches zero or more characters and ? matches exactly one character. The solution needs to handle these
# Intuition
The problem is a pattern-matching task where `*` matches zero or more characters and `?` matches exactly one character. The solution needs to handle these wildcards effectively while ensuring a match between the string `s` and the pattern `p`.

# Approach
The approach uses a greedy algorithm with two pointers: one for the string `s` and one for the pattern `p`. The main idea is:
1. Traverse the string `s` and the pattern `p` while handling three scenarios:
   - Characters match exactly, or `p[j]` is a `?`, which can match any single character. In this case, move both pointers forward.
   - `p[j]` is a `*`, which can match zero or more characters. Save the position of the `*` and the current position of `s` for backtracking.
   - If there is no match and there was a previous `*`, backtrack: revert `j` to the saved `*` position plus one, and increment the position of `s`.
2. After traversing `s`, ensure that the remaining characters in `p` are all `*` (as they can match zero characters).
3. Return true if the entire pattern is matched; otherwise, return false.

# Complexity
- **Time complexity**:  
  The algorithm traverses `s` and `p` at most twice in the worst-case scenario, resulting in a time complexity of $$O(n + m)$$, where `n` is the length of `s` and `m` is the length of `p`.

- **Space complexity**:  
  The algorithm uses a constant amount of extra space for variables like `i`, `j`, `star`, and `match`, resulting in a space complexity of $$O(1)$$.

# Code
Here is the solution with detailed comments explaining each part of the logic:

```cpp
class Solution {
public:
    bool isMatch(string s, string p) {
        // Initialize pointers for the string and pattern
        int i = 0, j = 0;
        // Variables to track the position of the last '*' in the pattern
        int star = -1, match = 0;
        
        // Traverse the string `s`
        while (i < s.size()) {
            if (j < p.size() && (p[j] == s[i] || p[j] == '?')) {
                // Case 1: Characters match or `?` matches any single character
                i++;
                j++;
            } else if (j < p.size() && p[j] == '*') {
                // Case 2: '*' can match zero or more characters
                star = j;    // Save the position of '*'
                match = i;   // Save the current position in `s` for backtracking
                j++;         // Move to the next character in the pattern
            } else if (star >= 0) {
                // Case 3: No match, but a previous '*' allows backtracking
                j = star + 1;  // Revert `j` to the position after '*'
                i = ++match;   // Increment `match` to include the next character in `s`
            } else {
                // Case 4: No match and no previous '*', return false
                return false;
            }
        }
        
        // Ensure the remaining characters in `p` are all `*`
        while (j < p.size() && p[j] == '*') {
            j++;
        }
        
        // If we have consumed the entire pattern, return true
        return j == p.size();
    }
};
```

### Explanation of Key Steps:
1. **Matching single characters or `?`:**  
   The `if` block ensures direct matches or single-character wildcard matches.

2. **Handling `*`:**  
   The `else if` block tracks the position of `*` and the corresponding match position in `s`, allowing backtracking later if needed.

3. **Backtracking:**  
   When a mismatch occurs, the `else if` block utilizes the saved `*` position to continue matching `s` from a new starting point.

4. **Final check for trailing `*`:**  
   Any remaining characters in `p` must all be `*` to ensure the pattern matches `s`.

This algorithm is efficient and handles all edge cases, such as empty patterns, consecutive `*`, and mixed usage of `*` and `?`.
['C++']