DP Solution, 4 different solutions
Recursive: Time Limit Exceeded\n\n\tTime Complexity: O(Exponential)\n\tSpace Complexity: O(N + M)\n\t\n\nclass Solution {\n    public boolean isMatch(String s, 
**Recursive:** Time Limit Exceeded\n\n\tTime Complexity: O(Exponential)\n\tSpace Complexity: O(N + M)\n\t\n```\nclass Solution {\n    public boolean isMatch(String s, String p) {\n        int n = p.length();\n        int m = s.length();\n        \n        return f(n - 1, m - 1, p, s);\n    }\n    \n    private boolean f(int i, int j, String p, String s) {\n        \n        // Base Case\n        \n        // if both strings get exhausted\n        if (i < 0 && j < 0) return true;\n        \n        // if one get exhausted and other didn\'t\n        if (i < 0 && j >= 0) return false;\n        \n        // if p is left, it has to be all \'*\'\n        if (j < 0 && i >= 0) {\n            for (int k = 0; k <= i; k++) {\n                if (p.charAt(k) != \'*\') {\n                    return false;\n                }\n            }\n            return true;\n        }\n        \n\n        // If match found or \'?\' is found \n        if (p.charAt(i) == s.charAt(j) || p.charAt(i) == \'?\') {\n            return f(i - 1, j - 1, p, s);\n        }\n        \n        // if it is a \'*\'\n        if (p.charAt(i) == \'*\') {\n            return f (i - 1, j, p, s) || f (i, j - 1, p, s);\n        }\n        \n        // No match found\n        return false;\n    }\n}\n```\n\n**Memoization:**\n\n\tTime Complexity: O(N x M)\n\tSpace Complexity: O(N x M) + O(N + M)\n\t\n```\nclass Solution {\n    public boolean isMatch(String s, String p) {\n        int n = p.length();\n        int m = s.length();\n        \n        int[][] dp = new int[n][m];\n        for (int[] row: dp) {\n            Arrays.fill(row, -1);\n        }\n        \n        return f(n - 1, m - 1, p, s, dp);\n    }\n    \n    private boolean f(int i, int j, String p, String s, int[][] dp) {\n        \n        // Base Case\n        \n        // if both strings get exhausted\n        if (i < 0 && j < 0) return true;\n        \n        // if one get exhausted and other didn\'t\n        if (i < 0 && j >= 0) return false;\n        \n        // if p is left, it has to be all \'*\'\n        if (j < 0 && i >= 0) {\n            for (int k = 0; k <= i; k++) {\n                if (p.charAt(k) != \'*\') {\n                    return false;\n                }\n            }\n            return true;\n        }\n        \n        \n        if (dp[i][j] != -1) {\n            return dp[i][j] == 1 ? true : false;\n        }\n        \n        // If match found or \'?\' is found \n        if (p.charAt(i) == s.charAt(j) || p.charAt(i) == \'?\') {\n            boolean flag = f(i - 1, j - 1, p, s, dp);\n            dp[i][j] = (flag == true) ? 1 : 0;\n            \n            return flag;\n        }\n        \n        // if it is a \'*\'\n        if (p.charAt(i) == \'*\') {\n            boolean flag = f (i - 1, j, p, s, dp) || f (i, j - 1, p, s, dp);\n            dp[i][j] = (flag == true) ? 1 : 0;\n            \n            return flag;\n        }\n        \n        // No match found\n        dp[i][j] = 0;\n        return false;\n    }\n}\n```\n\n**Tabulation:**\n\n\tTime Complexity: O(N x M)\n\tSpace Complexity: O(N x M)\n\t\n```\nclass Solution {\n    public boolean isMatch(String s, String p) {\n        int n = p.length();\n        int m = s.length();\n        \n        boolean[][] dp = new boolean[n + 1][m + 1];\n        \n        // Base Case\n        dp[0][0] = true;\n        \n        for (int j = 1; j <= m; j++) {\n            dp[0][j] = false;\n        }\n        \n        for (int i = 1; i <= n; i++) {\n            boolean flag = true;\n            for (int k = 1; k <= i; k++) {\n                if (p.charAt(k - 1) != \'*\') {\n                    flag = false;\n                    break;\n                }\n            }\n            dp[i][0] = flag;\n        }\n        \n        \n        \n        for (int i = 1; i <= n; i++) {\n            for (int j = 1; j <= m; j++) {\n                // If match found or \'?\' is found \n                if (p.charAt(i - 1) == s.charAt(j - 1) || p.charAt(i - 1) == \'?\') {\n                    dp[i][j] = dp[i - 1][j - 1];\n                }\n\n                // if it is a \'*\'\n                else if (p.charAt(i - 1) == \'*\') {\n                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];\n                }\n\n                // No match found\n                else dp[i][j] = false;\n            }\n        }\n        \n        return dp[n][m];\n    }\n}\n```\n\n**Space Optimised:**\n\n\tTime Complexity: O(N x M)\n\tSpace Complexity: O(M) + O(M)\n\t\n```\nclass Solution {\n    public boolean isMatch(String s, String p) {\n        int n = p.length();\n        int m = s.length();\n        \n        boolean[] prev = new boolean[m + 1];\n        \n        // Base Case\n        prev[0] = true;\n        \n        for (int j = 1; j <= m; j++) {\n            prev[j] = false;\n        }\n        \n        for (int i = 1; i <= n; i++) {\n            boolean[] cur = new boolean[m + 1];\n            \n            boolean flag = true;\n            for (int k = 1; k <= i; k++) {\n                if (p.charAt(k - 1) != \'*\') {\n                    flag = false;\n                    break;\n                }\n            }\n            cur[0] = flag;\n            \n            for (int j = 1; j <= m; j++) {\n                // If match found or \'?\' is found \n                if (p.charAt(i - 1) == s.charAt(j - 1) || p.charAt(i - 1) == \'?\') {\n                    cur[j] = prev[j - 1];\n                }\n\n                // if it is a \'*\'\n                else if (p.charAt(i - 1) == \'*\') {\n                    cur[j] = prev[j] || cur[j - 1];\n                }\n\n                // No match found\n                else cur[j] = false;\n            }\n            prev = cur;\n        }\n        \n        return prev[m];\n    }\n}\n\n// Please upvote if you find this helpful\n// Feel free to ask doubt\n```
['Dynamic Programming', 'Recursion', 'Java']