✅Easy and Optimal || 4 Approaches : Recursive || Memoization || Tabulation || Space Optimization
Intuition and Approach


Recursive Function Definition:
Define f(i, j) to check if s[0:i] matches p[0:j]:
i is the current index of the string s.
j is the curre
# Intuition and Approach
![WhatsApp Image 2025-01-01 at 21.49.56_79a0fc72.jpg](https://assets.leetcode.com/users/images/21a60b89-9dde-4809-9925-34a7113c6178_1735748445.3671153.jpeg)
![WhatsApp Image 2025-01-01 at 21.49.55_95adaf2d.jpg](https://assets.leetcode.com/users/images/7033e9dc-8e01-47f9-a501-41f47c8ea66f_1735748494.81349.jpeg)

1. Recursive Function Definition: 
    Define f(i, j) to check if s[0:i] matches p[0:j]:
    i is the current index of the string s.
    j is the current index of the pattern p.
2. Handling ?:
    If p[j] == '?',it matches any single character.Move both          indices: f(i-1, j-1).

3. Handling *:
can match zero or more characters. Two possibilities:
Skip *: f(i, j-1).
Use *: f(i-1, j).

4. Base Cases:
    Both i and j are 0: Return true (both strings are exhausted).
    Only one is 0: Return false (one string is exhausted).
    If p has remaining characters, ensure they are all *.

5. Exploration:
Explore all possibilities recursively to check if s matches p.

# Approach 1 : Recursive Approach
This approach uses recursion to check all possible matches between text and pattern. Wildcards ? match any single character, and * matches any sequence of characters. If either string is exhausted, conditions are checked recursively. This method explores all combinations, leading to exponential time complexity.

# Complexity
- Time complexity:$$O(2^n*2^m)$$
- Space complexity:$$O(n+m)$$

# Code
```cpp []
class Solution {
public:
    bool solve(int index1, int index2, string &text, string &pattern) {
        if (index1 < 0 && index2 < 0) return true;
        if (index2 < 0 && index1 >= 0) return false;
        if (index1 < 0 && index2 >= 0) {
            for (int i = 0; i <= index2; i++) {
                if (pattern[i] != '*') return false;
            }
            return true;
        }

        if (text[index1] == pattern[index2] || pattern[index2] == '?') {
            return solve(index1 - 1, index2 - 1, text, pattern);
        }

        if (pattern[index2] == '*') {
            return solve(index1 - 1, index2, text, pattern) || solve(index1, index2 - 1, text, pattern);
        }

        return false;
    }

    bool isMatch(string s, string p) {
        int n1 = s.size();
        int n2 = p.size();
        return solve(n1-1, n2-1, s, p);
    }
};
```
```java []
class Solution {
    public boolean solve(int index1, int index2, String text, String pattern) {
        if (index1 < 0 && index2 < 0) return true;
        if (index2 < 0 && index1 >= 0) return false;
        if (index1 < 0 && index2 >= 0) {
            for (int i = 0; i <= index2; i++) {
                if (pattern.charAt(i) != '*') return false;
            }
            return true;
        }

        if (text.charAt(index1) == pattern.charAt(index2) || pattern.charAt(index2) == '?') {
            return solve(index1 - 1, index2 - 1, text, pattern);
        }

        if (pattern.charAt(index2) == '*') {
            return solve(index1 - 1, index2, text, pattern) || solve(index1, index2 - 1, text, pattern);
        }

        return false;
    }

    public boolean isMatch(String s, String p) {
        int n1 = s.length();
        int n2 = p.length();
        return solve(n1 - 1, n2 - 1, s, p);
    }
}

```
```python []
class Solution:
    def solve(self, index1, index2, text, pattern):
        if index1 < 0 and index2 < 0:
            return True
        if index2 < 0 and index1 >= 0:
            return False
        if index1 < 0 and index2 >= 0:
            for i in range(index2 + 1):
                if pattern[i] != '*':
                    return False
            return True

        if text[index1] == pattern[index2] or pattern[index2] == '?':
            return self.solve(index1 - 1, index2 - 1, text, pattern)

        if pattern[index2] == '*':
            return self.solve(index1 - 1, index2, text, pattern) or self.solve(index1, index2 - 1, text, pattern)

        return False

    def isMatch(self, s: str, p: str) -> bool:
        n1 = len(s)
        n2 = len(p)
        return self.solve(n1 - 1, n2 - 1, s, p)

```

# Approach 2 : Memoization Approach
Memoization optimizes the recursive solution by storing intermediate results in a dp table. This avoids redundant computations by returning precomputed results when similar states are revisited. This approach significantly reduces the time complexity.
# Complexity
- Time complexity:$$O(n*m)$$
- Space complexity:$$O(n+m)$$[Recursive Stack Space]+$$O(n*m)$$[Dp Array]

# Code
```cpp []
class Solution {
public:
    bool solve(int index1, int index2, string &text, string &pattern,vector<vector<int>> &dp) {
        if (index1 < 0 && index2 < 0) return true;
        if (index2 < 0 && index1 >= 0) return false;
        if (index1 < 0 && index2 >= 0) {
            for (int i = 0; i <= index2; i++) {
                if (pattern[i] != '*') return false;
            }
            return true;
        }
        if(dp[index1][index2]!=-1){
            return dp[index1][index2];
        }
        if (text[index1] == pattern[index2] || pattern[index2] == '?') {
            return dp[index1][index2]=solve(index1 - 1, index2 - 1, text, pattern,dp);
        }

        if (pattern[index2] == '*') {
            return dp[index1][index2]=solve(index1 - 1, index2, text, pattern,dp) || solve(index1, index2 - 1, text, pattern,dp);
        }

        return dp[index1][index2]=false;
    }

    bool isMatch(string s, string p) {
        int n1 = s.size();
        int n2 = p.size();
        vector<vector<int>> dp(n1,vector<int>(n2,-1));
        return solve(n1-1, n2-1, s, p,dp);
    }
};
```
```java []
import java.util.Arrays;

class Solution {
    public boolean solve(int index1, int index2, String text, String pattern, int[][] dp) {
        if (index1 < 0 && index2 < 0) return true;
        if (index2 < 0 && index1 >= 0) return false;
        if (index1 < 0 && index2 >= 0) {
            for (int i = 0; i <= index2; i++) {
                if (pattern.charAt(i) != '*') return false;
            }
            return true;
        }
        if (dp[index1][index2] != -1) {
            return dp[index1][index2] == 1;
        }

        if (text.charAt(index1) == pattern.charAt(index2) || pattern.charAt(index2) == '?') {
            dp[index1][index2] = solve(index1 - 1, index2 - 1, text, pattern, dp) ? 1 : 0;
        } else if (pattern.charAt(index2) == '*') {
            dp[index1][index2] = (solve(index1 - 1, index2, text, pattern, dp) || solve(index1, index2 - 1, text, pattern, dp)) ? 1 : 0;
        } else {
            dp[index1][index2] = 0;
        }
        return dp[index1][index2] == 1;
    }

    public boolean isMatch(String s, String p) {
        int n1 = s.length();
        int n2 = p.length();
        int[][] dp = new int[n1][n2];
        for (int[] row : dp) {
            Arrays.fill(row, -1);
        }

```
```python []
class Solution:
    def solve(self, index1, index2, text, pattern, dp):
        if index1 < 0 and index2 < 0:
            return True
        if index2 < 0 and index1 >= 0:
            return False
        if index1 < 0 and index2 >= 0:
            for i in range(index2 + 1):
                if pattern[i] != '*':
                    return False
            return True
        if dp[index1][index2] != -1:
            return dp[index1][index2] == 1

        if text[index1] == pattern[index2] or pattern[index2] == '?':
            dp[index1][index2] = int(self.solve(index1 - 1, index2 - 1, text, pattern, dp))
        elif pattern[index2] == '*':
            dp[index1][index2] = int(self.solve(index1 - 1, index2, text, pattern, dp) or self.solve(index1, index2 - 1, text, pattern, dp))
        else:
            dp[index1][index2] = 0
        return dp[index1][index2] == 1

    def isMatch(self, s: str, p: str) -> bool:
        n1 = len(s)
        n2 = len(p)
        dp = [[-1 for _ in range(n2)] for _ in range(n1)]
        return self.solve(n1 - 1, n2 - 1, s, p, dp)

```


# Approach 3 : Tabulation Approach
This bottom-up dynamic programming approach fills a dp table iteratively. Each cell represents whether the substring of text up to index i matches the substring of pattern up to index j. The result is stored in the last cell. 
# Complexity
- Time complexity:$$O(n*m)$$
- Space complexity:$$O(n*m)$$[Dp Array]

# Code
```cpp []
class Solution {
public:
    bool isMatch(string text, string pattern) {
        int n1 = text.size();
        int n2 = pattern.size();
        vector<vector<bool>> dp(n1+1, vector<bool>(n2+1, false));
        dp[0][0] = true;
        for (int j = 1; j <= n2; j++) {
            if (pattern[j - 1] == '*') dp[0][j] = dp[0][j - 1];
        }
        for (int i = 1; i <= n1; i++) {
            dp[i][0] = false;
        }
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (text[i - 1] == pattern[j - 1] || pattern[j - 1] == '?') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (pattern[j - 1] == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                } else {
                    dp[i][j] = false;
                }
            }
        }
        return dp[n1][n2];
    }
};
```
```java []

class Solution {
    public boolean isMatch(String text, String pattern) {
        int n1 = text.length();
        int n2 = pattern.length();
        boolean[][] dp = new boolean[n1 + 1][n2 + 1];

        dp[0][0] = true;

        // Handle the pattern for leading '*' characters
        for (int j = 1; j <= n2; j++) {
            if (pattern.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 1];
            }
        }

        // Fill the dp table
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (text.charAt(i - 1) == pattern.charAt(j - 1) || pattern.charAt(j - 1) == '?') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (pattern.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                } else {
                    dp[i][j] = false;
                }
            }
        }

        return dp[n1][n2];
    }
}
```
```python []
class Solution:
    def isMatch(self, text: str, pattern: str) -> bool:
        n1, n2 = len(text), len(pattern)
        dp = [[False] * (n2 + 1) for _ in range(n1 + 1)]

        dp[0][0] = True

        # Handle the pattern for leading '*' characters
        for j in range(1, n2 + 1):
            if pattern[j - 1] == '*':
                dp[0][j] = dp[0][j - 1]

        # Fill the dp table
        for i in range(1, n1 + 1):
            for j in range(1, n2 + 1):
                if text[i - 1] == pattern[j - 1] or pattern[j - 1] == '?':
                    dp[i][j] = dp[i - 1][j - 1]
                elif pattern[j - 1] == '*':
                    dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
                else:
                    dp[i][j] = False

        return dp[n1][n2]

```

# Approach 4 : Space Optimization
Space optimization reduces the dp table to two 1D arrays (prev and curr), representing the current and previous rows of the table. By overwriting results, memory usage is minimized to $$O(n)$$
# Complexity
- Time complexity:$$O(n*m)$$
- Space complexity:$$O(n)$$

# Code
```cpp []
class Solution {
public:
    bool isMatch(string text, string pattern) {
        int n1 = text.size();
        int n2 = pattern.size();
        vector<bool> prev(n2 + 1, false), curr(n2 + 1, false);
        prev[0] = true;

        for (int j = 1; j <= n2; j++) {
            if (pattern[j - 1] == '*') {
                prev[j] = prev[j - 1];
            }
        }

        if (n2 == 0 && n1 > 0) {
            return false;
        }

        for (int i = 1; i <= n1; i++) {
            bool flag = true;
            for (int j = 1; j <= n2; j++) {
                if (pattern[j - 1] != '*') {
                    flag = false;
                    break;
                }
            }
            curr[0] = flag;
            for (int j = 1; j <= n2; j++) {
                if (text[i - 1] == pattern[j - 1] || pattern[j - 1] == '?') {
                    curr[j] = prev[j - 1];
                } else if (pattern[j - 1] == '*') {
                    curr[j] = prev[j] || curr[j - 1];
                } else {
                    curr[j] = false;
                }
            }
            prev = curr;
        }

        return prev[n2];
    }
};
```
```java []
class Solution {
    public boolean isMatch(String text, String pattern) {
        int n1 = text.length();
        int n2 = pattern.length();
        boolean[] prev = new boolean[n2 + 1];
        boolean[] curr = new boolean[n2 + 1];
        prev[0] = true;

        for (int j = 1; j <= n2; j++) {
            if (pattern.charAt(j - 1) == '*') {
                prev[j] = prev[j - 1];
            }
        }

        if (n2 == 0 && n1 > 0) {
            return false;
        }

        for (int i = 1; i <= n1; i++) {
            boolean flag = true;
            for (int j = 1; j <= n2; j++) {
                if (pattern.charAt(j - 1) != '*') {
                    flag = false;
                    break;
                }
            }
            curr[0] = flag;

            for (int j = 1; j <= n2; j++) {
                if (text.charAt(i - 1) == pattern.charAt(j - 1) || pattern.charAt(j - 1) == '?') {
                    curr[j] = prev[j - 1];
                } else if (pattern.charAt(j - 1) == '*') {
                    curr[j] = prev[j] || curr[j - 1];
                } else {
                    curr[j] = false;
                }
            }

            // Swap curr and prev for next iteration
            boolean[] temp = prev;
            prev = curr;
            curr = temp;
        }

        return prev[n2];
    }
}
```
```python []
class Solution:
    def isMatch(self, text: str, pattern: str) -> bool:
        n1, n2 = len(text), len(pattern)
        prev = [False] * (n2 + 1)
        curr = [False] * (n2 + 1)
        prev[0] = True

        for j in range(1, n2 + 1):
            if pattern[j - 1] == '*':
                prev[j] = prev[j - 1]

        if n2 == 0 and n1 > 0:
            return False

        for i in range(1, n1 + 1):
            flag = all(pattern[k - 1] == '*' for k in range(1, n2 + 1))
            curr[0] = flag

            for j in range(1, n2 + 1):
                if text[i - 1] == pattern[j - 1] or pattern[j - 1] == '?':
                    curr[j] = prev[j - 1]
                elif pattern[j - 1] == '*':
                    curr[j] = prev[j] or curr[j - 1]
                else:
                    curr[j] = False

            # Swap curr and prev for next iteration
            prev, curr = curr, prev

        return prev[n2]

```

['String', 'Dynamic Programming', 'Recursion', 'C++', 'Java', 'Python3']