Intuition to Space Optimized ✅💯🚀
\n\n# Code\njava []\n// Approach -1\n\nclass Solution {\n    public boolean isMatch(String s, String p) {\n        return wildcardMatching(p, s) == 1;\n    }\n 
\n\n# Code\n```java []\n// Approach -1\n\nclass Solution {\n    public boolean isMatch(String s, String p) {\n        return wildcardMatching(p, s) == 1;\n    }\n    \n    private static boolean isAllStars(String S1, int i) {\n        for (int j = 0; j <= i; j++) {\n            if (S1.charAt(j) != \'*\')\n                return false;\n        }\n        return true;\n    }\n\n    private static int wildcardMatchingUtil(String S1, String S2, int i, int j, int[][] dp) {\n        if (i < 0 && j < 0)\n            return 1;\n        if (i < 0 && j >= 0)\n            return 0;\n        if (j < 0 && i >= 0)\n            return isAllStars(S1, i) ? 1 : 0;\n\n        if (dp[i][j] != -1) return dp[i][j];\n\n        if (S1.charAt(i) == S2.charAt(j) || S1.charAt(i) == \'?\')\n            return dp[i][j] = wildcardMatchingUtil(S1, S2, i - 1, j - 1, dp);\n        else {\n            if (S1.charAt(i) == \'*\') {\n                return dp[i][j] = (wildcardMatchingUtil(S1, S2, i - 1, j, dp) == 1 || wildcardMatchingUtil(S1, S2, i, j - 1, dp) == 1) ? 1 : 0;\n            } else {\n                return dp[i][j] = 0;\n            }\n        }\n    }\n\n    private static int wildcardMatching(String S1, String S2) {\n        int n = S1.length();\n        int m = S2.length();\n\n        int dp[][] = new int[n][m];\n        for (int row[] : dp)\n            Arrays.fill(row, -1);\n\n        return wildcardMatchingUtil(S1, S2, n - 1, m - 1, dp);\n    }\n}\n```\n```java []\n// Approach -1\n\npublic class Solution {\n    public boolean isMatch(String s, String p) {\n        int n = p.length(); // Length of the pattern\n        int m = s.length(); // Length of the text\n\n        // Create a 2D array to store the result of subproblems\n        int[][] dp = new int[n + 1][m + 1];\n        for (int[] row : dp) {\n            Arrays.fill(row, -1);\n        }\n\n        // Call the recursive helper function to perform wildcard matching\n        return isMatchUtil(p, s, n - 1, m - 1, dp) == 1;\n    }\n\n    // Helper method to check if the pattern matches the text\n    static int isMatchUtil(String pattern, String text, int i, int j, int[][] dp) {\n        // Base Cases\n        if (i < 0 && j < 0) {\n            return 1; // Both strings are empty, and the pattern matches.\n        }\n        if (i < 0 && j >= 0) {\n            return 0; // Pattern is empty, but there are characters left in text.\n        }\n        if (j < 0 && i >= 0) {\n            // Text is empty, check if remaining characters in pattern are all \'*\'.\n            return isAllStars(pattern, i) ? 1 : 0;\n        }\n\n        // If the result is already computed, return it.\n        if (dp[i][j] != -1) {\n            return dp[i][j];\n        }\n\n        // If the characters match or pattern has a \'?\', continue matching the rest of the strings.\n        if (pattern.charAt(i) == text.charAt(j) || pattern.charAt(i) == \'?\') {\n            return dp[i][j] = isMatchUtil(pattern, text, i - 1, j - 1, dp);\n        } else {\n            if (pattern.charAt(i) == \'*\') {\n                // Two possibilities when encountering \'*\':\n                // 1. \'*\' matches one or more characters in text.\n                // 2. \'*\' matches zero characters in text.\n                return dp[i][j] = (isMatchUtil(pattern, text, i - 1, j, dp) == 1 || isMatchUtil(pattern, text, i, j - 1, dp) == 1) ? 1 : 0;\n            } else {\n                // Characters don\'t match, and pattern[i] is not \'*\'.\n                return 0;\n            }\n        }\n    }\n\n    // Helper method to check if the remaining characters in the pattern are all \'*\'\n    static boolean isAllStars(String pattern, int i) {\n        for (int j = 0; j <= i; j++) {\n            if (pattern.charAt(j) != \'*\') {\n                return false;\n            }\n        }\n        return true;\n    }\n}\n\n```\n```java []\n\n\n// Approach -2\n\nclass Solution {\n    public boolean isMatch(String s, String p) {\n        int n = p.length();\n        int m = s.length();\n\n        // Create a 2D array to store the matching results\n        boolean dp[][] = new boolean[n + 1][m + 1];\n        dp[0][0] = true;\n\n        // Initialize the first row and column based on wildcard \'*\' in p\n        for (int j = 1; j <= m; j++) {\n            dp[0][j] = false;\n        }\n        for (int i = 1; i <= n; i++) {\n            dp[i][0] = isAllStars(p, i);\n        }\n\n        // Fill the dp array using a bottom-up approach\n        for (int i = 1; i <= n; i++) {\n            for (int j = 1; j <= m; j++) {\n                if (p.charAt(i - 1) == s.charAt(j - 1) || p.charAt(i - 1) == \'?\') {\n                    dp[i][j] = dp[i - 1][j - 1]; // Characters match or \'?\' is encountered.\n                } else {\n                    if (p.charAt(i - 1) == \'*\') {\n                        dp[i][j] = dp[i - 1][j] || dp[i][j - 1]; // \'*\' matches one or more characters.\n                    } else {\n                        dp[i][j] = false; // Characters don\'t match, and p[i-1] is not \'*\'.\n                    }\n                }\n            }\n        }\n\n        return dp[n][m]; // The final result indicates whether p matches s.\n    }\n\n    private boolean isAllStars(String p, int i) {\n        for (int j = 1; j <= i; j++) {\n            if (p.charAt(j - 1) != \'*\')\n                return false;\n        }\n        return true;\n    }\n}\n```\n```java []\n//Approach -3\n\nclass Solution {\n    \n\n    public boolean isMatch(String s, String p) {\n        int n = p.length();\n        int m = s.length();\n\n        // Create two boolean arrays to store the matching results for the current and previous rows\n        boolean[] prev = new boolean[m + 1];\n        boolean[] cur = new boolean[m + 1];\n\n        // Initialize the first element of prev as true\n        prev[0] = true;\n\n        // Iterate through p and s to fill the cur array\n        for (int i = 1; i <= n; i++) {\n            // Initialize the first element of cur based on whether p contains \'*\'\n            cur[0] = isAllStars(p, i);\n            for (int j = 1; j <= m; j++) {\n                if (p.charAt(i - 1) == s.charAt(j - 1) || p.charAt(i - 1) == \'?\') {\n                    cur[j] = prev[j - 1]; // Characters match or \'?\' is encountered.\n                } else {\n                    if (p.charAt(i - 1) == \'*\') {\n                        cur[j] = prev[j] || cur[j - 1]; // \'*\' matches one or more characters.\n                    } else {\n                        cur[j] = false; // Characters don\'t match, and p[i-1] is not \'*\'.\n                    }\n                }\n            }\n            // Update prev array to store the current values\n            prev = cur.clone();\n        }\n\n        return prev[m]; // The final result indicates whether p matches s.\n    }\n    \n    private boolean isAllStars(String p, int i) {\n        for (int j = 1; j <= i; j++) {\n            if (p.charAt(j - 1) != \'*\') {\n                return false;\n            }\n        }\n        return true;\n    }\n}\n\n```
['String', 'Dynamic Programming', 'Recursion', 'Java']