C++ || Recursion -> Memoization ->Tabulation
RECURSION (TLE)\n\nclass Solution {\npublic:\n    bool f(int i,int j, string &s,string &p)\n    {\n        if(i<0 && j<0) return true;\n        if(j<0 && i>=0) 
**RECURSION (TLE)**\n```\nclass Solution {\npublic:\n    bool f(int i,int j, string &s,string &p)\n    {\n        if(i<0 && j<0) return true;\n        if(j<0 && i>=0) return false;\n        if(i<0 && j>=0)\n        {\n            while(j>=0)\n            {\n                if(p[j]==\'*\') j--;\n                else return false;\n            }\n            return true;\n        }\n        \n        if(s[i]==p[j] || p[j]==\'?\') return f(i-1,j-1,s,p);\n        \n        if(p[j]==\'*\')\n        {\n            return f(i-1,j,s,p) || f(i,j-1,s,p);\n            //Two cases\n            //Consider * as len=0\n            //Give one charcter to * and remain at *\n            //at next step it will again be decided from both these cases\n        }\n        return false;\n        \n    }\n    \n    bool isMatch(string s, string p) {\n        int n=s.length(),m=p.length();\n        return f(n-1,m-1,s,p);\n    }\n};\n```\n**Memoization**\n```\nclass Solution {\npublic:\n    int f(int i,int j, string &s,string &p,vector<vector<int>> &dp)\n    {\n        if(dp[i][j]!=-1) return dp[i][j];\n        if(i==0 && j==0) return dp[i][j]=1;\n        if(j==0 && i>0) return dp[i][j]=0;\n        if(i==0 && j>0)\n        {\n            while(j>0)\n            {\n                if(p[j-1]==\'*\') j--;\n                else return dp[i][j]=0;\n            }\n            return dp[i][j]=1;\n        }\n        \n        if(s[i-1]==p[j-1] || p[j-1]==\'?\') return dp[i][j]=f(i-1,j-1,s,p,dp);\n        \n        if(p[j-1]==\'*\')\n        {\n            return dp[i][j] = f(i-1,j,s,p,dp) || f(i,j-1,s,p,dp) ? 1:0;\n            //Two cases\n            //Consider * as len=0\n            //Give one charcter to * and remain at *\n            //at next step it will again be decided from both these cases\n        }\n        return dp[i][j]=0;\n        \n    }\n    \n    bool isMatch(string s, string p) {\n        int n=s.length(),m=p.length();\n        vector<vector<int>> dp(n+1,vector<int>(m+1,-1));\n        return f(n,m,s,p,dp);\n    }\n};\n```\n**Tabulation**\n```\nclass Solution {\npublic:\n    bool isMatch(string s, string p) {\n        int n=s.length(),m=p.length();\n        vector<vector<bool>> dp(n+1,vector<bool>(m+1));\n        dp[0][0]=true;\n        for(int i=1;i<=n;i++) dp[i][0]=false;\n        \n        bool flag=true;\n        for(int i=1;i<=m;i++)\n        {\n            if(p[i-1]!=\'*\')\n                flag=false;\n            dp[0][i]=flag;\n        }\n        for(int i=1;i<=n;i++)\n        {\n            for(int j=1;j<=m;j++)\n            {\n                if(s[i-1]==p[j-1] || p[j-1]==\'?\')\n                    dp[i][j]=dp[i-1][j-1];\n                else if(p[j-1]==\'*\')\n                    dp[i][j] = dp[i-1][j] || dp[i][j-1];\n                else dp[i][j]=false;\n            }\n        }\n        return dp[n][m];\n    }\n};\n```\n**Space Optimized**\n```\nclass Solution {\npublic:\n    bool isMatch(string s, string p) {\n        int n=s.length(),m=p.length();\n        // vector<vector<bool>> dp(n+1,vector<bool>(m+1));\n        \n        vector<bool> prev(m+1);\n        //Initially prev is for n=0\n        prev[0]=true;\n        \n        bool flag=true;\n        for(int i=1;i<=m;i++)\n        {\n            if(p[i-1]!=\'*\')\n                flag=false;\n            prev[i]=flag;\n        }\n        vector<bool> curr(m+1);\n        \n        \n        for(int i=1;i<=n;i++)\n        {\n            curr[0]=false;\n            for(int j=1;j<=m;j++)\n            {\n                if(s[i-1]==p[j-1] || p[j-1]==\'?\')\n                    curr[j]=prev[j-1];\n                else if(p[j-1]==\'*\')\n                    curr[j] = prev[j] || curr[j-1];\n                else curr[j]=false;\n            }\n            prev=curr;\n        }\n        return prev[m];\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'C', 'C++']