Java Solution | Memoization + Tabulation | DP
Here I am both types of DP solution, Memoization and Tabulation.\nYou will get TLE in memoization solution.\n\nIf you like the solution, then please UPVOTE it :
Here I am both types of DP solution, Memoization and Tabulation.\nYou will get TLE in memoization solution.\n\nIf you like the solution, then please UPVOTE it :)\n\nMemoization Solution\n```\nclass Solution {\n    public boolean isMatch(String s, String p) {\n        int i = s.length();\n        int j = p.length();\n        if(j == 0 && i!= 0)\n            return false;\n        \n        boolean[][] dp = new boolean[i][j];\n        return match(s,p,i-1,j-1,dp);\n    }\n    \n    public boolean match(String s , String p , int i , int j , boolean[][] dp)\n    {\n        if(i < 0 && j < 0)\n            return true;\n        \n        if(i < 0){\n            for(int k = 0 ; k <= j ; k++)\n                if(p.charAt(k) != \'*\')\n                    return false;\n            \n            return true;\n        }\n        \n        if(j < 0)\n        {\n            return false;\n        }\n        \n        if(dp[i][j])\n            return dp[i][j];\n        \n        if(s.charAt(i) == p.charAt(j) || p.charAt(j) == \'?\') dp[i][j] = match(s,p,i-1,j-1,dp);\n        else if(p.charAt(j) == \'*\') dp[i][j] = match(s,p,i-1,j,dp) | match(s,p,i,j-1,dp);\n        \n        return dp[i][j];\n        \n    }\n}\n```\n\nTabulation Solution\n```\nclass Solution {\n    public boolean isMatch(String s, String p) {\n        int i = s.length();\n        int j = p.length();\n        \n        boolean[][] dp = new boolean[i+1][j+1];\n        \n        dp[0][0] = true;\n        \n        for (int k = 1; k < j + 1; k++) {\n            if (p.charAt(k - 1) == \'*\') {\n                dp[0][k] = dp[0][k-1];\n            }\n        }\n        \n        \n        for(int x = 1 ; x <= i ; x++)\n        {\n            for(int y = 1 ; y <= j ; y++){\n                if(s.charAt(x-1) == p.charAt(y-1) || p.charAt(y-1) == \'?\')   \n                    dp[x][y] = dp[x-1][y-1];\n                else if(p.charAt(y-1) == \'*\')   \n                    dp[x][y] = (dp[x-1][y] | dp[x][y-1]);\n            }\n        }\n        \n        return dp[i][j];\n    }\n}\n```\n\nHaven\'t UPVOTED yet, can do it now :)
['Dynamic Programming', 'Memoization', 'Java']