✅C++ || Recursion->Memoization->Tabulation->SpaceOptimization
Method - 1 [Recursion] \n\n\n\tclass Solution {\n\tpublic:\n\t\tbool f(int i,int j,string& p,string& s){\n\t\t\tif(i<0 && j<0) return true;\n\t\t\tif(i<0 && j>=
# Method - 1 [Recursion] \n![image](https://assets.leetcode.com/users/images/51e10645-e2f4-4b78-b2bd-7880beb409cb_1661582208.273855.png)\n\n\tclass Solution {\n\tpublic:\n\t\tbool f(int i,int j,string& p,string& s){\n\t\t\tif(i<0 && j<0) return true;\n\t\t\tif(i<0 && j>=0) return false;\n\t\t\tif(j<0 && i>=0){\n\t\t\t\tfor(int k=i;k>=0;k--){\n\t\t\t\t\tif(p[k]!=\'*\') return false;\n\t\t\t\t}\n\t\t\t\treturn true;\n\t\t\t}\n\t//      Match \n\t\t\tif(p[i]==s[j] || p[i]==\'?\') return f(i-1,j-1,p,s);\n\t\t\tif(p[i]==\'*\') return f(i-1,j,p,s) || f(i,j-1,p,s);\n\t//      NotMatch\n\t\t\treturn false;\n\t\t}\n\n\t\tbool isMatch(string s, string p) {\n\t\t\tint n=p.size();\n\t\t\tint m=s.size();\n\t\t\treturn f(n-1,m-1,p,s);\n\t\t}\n\t};\n\t\n# Method - 2 [Memoization]\t\n![image](https://assets.leetcode.com/users/images/49215323-5577-4559-90a2-e8d8ec335fcc_1661582342.8689756.png)\n\n\tclass Solution {\n\tpublic:\n\t\tbool f(int i,int j,string& p,string& s,vector<vector<int>>& dp){\n\t\t\tif(i<0 && j<0) return true;\n\t\t\tif(i<0 && j>=0) return false;\n\t\t\tif(j<0 && i>=0){\n\t\t\t\tfor(int k=i;k>=0;k--){\n\t\t\t\t\tif(p[k]!=\'*\') return false;\n\t\t\t\t}\n\t\t\t\treturn true;\n\t\t\t}\n\t\t\tif(dp[i][j]!=-1) return dp[i][j];\n\t//      Match \n\t\t\tif(p[i]==s[j] || p[i]==\'?\') return dp[i][j]=f(i-1,j-1,p,s,dp);\n\t\t\tif(p[i]==\'*\') return dp[i][j]=f(i-1,j,p,s,dp) || f(i,j-1,p,s,dp);\n\t//      NotMatch\n\t\t\treturn dp[i][j]=false;\n\t\t}\n\n\t\tbool isMatch(string s, string p) {\n\t\t\tint n=p.size();\n\t\t\tint m=s.size();\n\t\t\tvector<vector<int>> dp(n,vector<int>(m,-1));\n\t\t\treturn f(n-1,m-1,p,s,dp);\n\t\t}\n\t};\n\n# Method - 3 [Tabulation]\n\n![image](https://assets.leetcode.com/users/images/de78b6e7-c220-4b83-8fb3-2b9031909db2_1661593846.1921206.png)\n\n**T->O(mn) && S->O(mn)**\n\n\tclass Solution {\n\tpublic:\n\t\tbool isMatch(string s, string p) {\n\t\t\tint n=p.size();\n\t\t\tint m=s.size();\n\t\t\tvector<vector<bool>> dp(n+1,vector<bool>(m+1,false));\n\t\t\tdp[0][0]=true;\n\t\t\tfor(int j=1;j<=m;j++) dp[0][j]=false;\n\t\t\tfor(int i=1;i<=n;i++){\n\t\t\t\tbool flag=true;\n\t\t\t\tfor(int k=1;k<=i;k++){\n\t\t\t\t\tif(p[k-1]!=\'*\'){\n\t\t\t\t\t\tflag=false;\n\t\t\t\t\t\tbreak;\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t\tdp[i][0]=flag;\n\t\t\t}\n\t\t\tfor(int i=1;i<=n;i++){\n\t\t\t\tfor(int j=1;j<=m;j++){\n\t\t\t\t\tif(p[i-1]==s[j-1] || p[i-1]==\'?\') dp[i][j]=dp[i-1][j-1];\n\t\t\t\t\telse if(p[i-1]==\'*\') dp[i][j]=dp[i-1][j] || dp[i][j-1];\n\t\t\t\t\telse dp[i][j]=false;\n\t\t\t\t}\n\t\t\t}\n\t\t\treturn dp[n][m];\n\t\t}\n\t};\n\t\n# Method - 4 [SpaceOptimization]\n\n![image](https://assets.leetcode.com/users/images/d723d4e6-b015-489c-8bed-ef95f203be68_1661594465.8915417.png)\n\n**T->O(nm) && S->O(m)**\n\n\tclass Solution {\n\tpublic:\n\t\tbool isMatch(string s, string p) {\n\t\t\tint n=p.size();\n\t\t\tint m=s.size();\n\t\t\tvector<bool> prev(m+1,false),curr(m+1,false);\n\t\t\tprev[0]=true;\n\t\t\tfor(int i=1;i<=n;i++){\n\t\t\t\tbool flag=true;\n\t\t\t\tfor(int k=1;k<=i;k++){\n\t\t\t\t\tif(p[k-1]!=\'*\'){\n\t\t\t\t\t\tflag=false;\n\t\t\t\t\t\tbreak;\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t\tcurr[0]=flag;\n\t\t\t\tfor(int j=1;j<=m;j++){\n\t\t\t\t\tif(p[i-1]==s[j-1] || p[i-1]==\'?\') curr[j]=prev[j-1];\n\t\t\t\t\telse if(p[i-1]==\'*\') curr[j]=prev[j] || curr[j-1];\n\t\t\t\t\telse curr[j]=false;\n\t\t\t\t}\n\t\t\t\tprev=curr;\n\t\t\t}\n\t\t\treturn prev[m];\n\t\t}\n\t};
['Dynamic Programming', 'Recursion', 'Memoization', 'C', 'C++']