C++ || Detailed Explaination || From Recursive to Space optimisation
Approach:\n\n--> In this problem, we have to match p with s so here we can use string matching method in which we use 2 variables i and j and check for each cha
## Approach:\n\n--> In this problem, we have to match `p` with `s` so here we can use string matching method in which we use 2 variables `i and j` and check for each character if they are matching or not.\n\n### If characters are matching:\n\nNow here we also have one extra condition which will be `if p[i] is \'?\'` and if it\'s true then also we will consider it as match because `?` can match with any single character.\n\nSo for both of these conditions we will simply decrease both `i and j`.\n\n```cpp\nif(p[i] == s[j] || p[i] == \'?\'){\n\treturn solve(i-1,j-1);\n}\n```\n\n### If p[i] is \'*\':\n\n--> now here we have 2 conditions:\n\n1. If we assume `\'*\'` as sequence of length 0 (means empty string)\nthen we will simply decrease `i` and keep `j` as it is.\n2. If we assume `\'*\'` as p[i]\nthen we will decrease `j`.\n\n--> we have to do this for every character because `*` can have any length of subsequence so we will have check all possibilities:\n\nthis recursive tree will look like this:\n\n![image](https://assets.leetcode.com/users/images/c61364a5-4e1b-42ce-9435-65e3f00ccd20_1663254206.0240915.png)\n\n```cpp\nif(p[i] == \'*\'){\n\treturn solve(i-1,j) || solve(i,j-1);\n}\n```\n\n### If p[i] and s[j] are not matching:\n\nthen we will simply return `false`\n\n## Base case:\n\n--> So in base case, there can be 2 possibilities:\n\n1. If we have traversed the p string means i is negative:\n\nthen we will check if `j is also negative` and if it is then we will return `true` because both strings got traversed and if `j is not negative` then we will return `false`.\n\n```cpp\nif(i<0){\n\treturn j<0;\n}\n```\n\n2. If we have traversed the s string means j is negative:\n\nHere we can compare empty string with only one thing which is `\'*\'` so if p have all characters as `*` then we will return true otherwise we will return false.\n\n```cpp\nif(j<0){\n\tfor(int k=0;k<=i;k++){\n\t\tif(p[k] != \'*\'){\n\t\t\treturn false;\n\t\t}\n\t}\n\treturn true;\n}\n```\n\n## Recursive Code:\n\n```cpp\n bool solve(int i,int j,string s,string p){\n\tif(i<0){\n\t\treturn j<0;\n\t}\n\tif(j<0){\n\t\tfor(int k=0;k<=i;k++){\n\t\t\tif(p[k] != \'*\'){\n\t\t\t\treturn false;\n\t\t\t}\n\t\t}\n\t\treturn true;\n\t}\n\tif(p[i] == s[j] || p[i] == \'?\'){\n\t\treturn solve(i-1,j-1,s,p);\n\t}\n\telse if(p[i] == \'*\'){\n\t\treturn solve(i-1,j,s,p) || solve(i,j-1,s,p);\n\t}\n\t// if they are not matching\n\treturn false;\n}\nbool isMatch(string s, string p) {\n\treturn solve(p.size()-1,s.size()-1,s,p);\n}\n```\n\n## Memoization Code:\n\n```cpp\nbool solve(int i,int j,string s,string p,vector<vector<int>>&dp){\n\tif(i<0){\n\t\treturn j<0;\n\t}\n\tif(j<0){\n\t\tfor(int k=0;k<=i;k++){\n\t\t\tif(p[k] != \'*\'){\n\t\t\t\treturn false;\n\t\t\t}\n\t\t}\n\t\treturn true;\n\t}\n\tif(dp[i][j] != -1){\n\t\treturn dp[i][j];\n\t}\n\tif(p[i] == s[j] || p[i] == \'?\'){\n\t\treturn dp[i][j] = solve(i-1,j-1,s,p,dp);\n\t}\n\telse if(p[i] == \'*\'){\n\t\treturn dp[i][j] = solve(i-1,j,s,p,dp) || solve(i,j-1,s,p,dp);\n\t}\n\t// if they are not matching\n\treturn dp[i][j] = false;\n}\nbool isMatch(string s, string p) {\n\tint n = p.size(),m = s.size();\n\tvector<vector<int>>dp(n+1,vector<int>(m,-1));\n\treturn solve(n-1,m-1,s,p,dp);\n}\n```\n\n## Tabulation Code:\n\n--> So in tabulation first we will write the base condition and also we have to change one thing which will ` we will use 1 based indexing` because in recursive code we are stopping at i or j becoming negative but we can\'t do it here so we will use 1 based indexing.\n\nNow let\'s see all base cases one by one:\n\n1. If i is 0 and j is also 0 then we will mark it as `true`\n```cpp\ndp[0][0] = true\n```\n\n2. if i is 0 and j is greater than 0 then we will mark it as `false`.\n\n```cpp\nfor(int j=1;j<=m;j++){\n\tdp[0][j] = false;\n}\n```\n\n3. if j is 0 then p must have all characters as `\'*\'` so that it can be matched with empty string.\n\n```cpp\n// starting from 1 because it\'s 1 based indexing.\nfor(int i=1;i<=n;i++){\n\tbool flag = true;\n\tfor(int k=1;k<=i;k++){\n\t\tif(p[k-1] != \'*\'){\n\t\t\tflag = false;\n\t\t\tbreak;\n\t\t}\n\t}\n\tdp[i][0] = flag;\n}\n```\n\nNow after base case we will just have to run one loop from i from `1 to n` and one nested loop for j from `1 to m` and just copy paste the logic from recursion code:\n\n```cpp\nbool isMatch(string s, string p) {\n        int n = p.size(),m = s.size();\n        vector<vector<bool>>dp(n+1,vector<bool>(m+1,false));\n        // case 1\n        dp[0][0] = true;\n        // case 2\n        for(int j=1;j<=m;j++){\n            dp[0][j] = false;\n        }\n        // case 3\n        for(int i=1;i<=n;i++){\n            bool flag = true;\n            for(int k=1;k<=i;k++){\n                if(p[k-1] != \'*\'){\n                    flag = false;\n                    break;\n                }\n            }\n            dp[i][0] = flag;\n        }\n        for(int i=1;i<=n;i++){\n            for(int j=1;j<=m;j++){\n                if(p[i-1] == s[j-1] || p[i-1] == \'?\'){\n                    dp[i][j] = dp[i-1][j-1];\n                }else if(p[i-1] == \'*\'){\n                    dp[i][j] = dp[i][j-1] || dp[i-1][j];\n                }else{\n                    dp[i][j] = false;\n                }\n            }\n        }\n        return dp[n][m];\n    }\n```\n\n## Space optimisation:\n\n```cpp\nbool isMatch(string s, string p) {\n        int n = p.size(),m = s.size();\n        vector<bool>prev(m+1,0),curr(m+1,0);\n        // case 1\n        prev[0] = true;\n        // case 2\n        for(int j=1;j<=m;j++){\n            prev[j] = false;\n        }\n        for(int i=1;i<=n;i++){\n\t        // case 3\n            bool flag = true;\n            for(int k=1;k<=i;k++){\n                if(p[k-1] != \'*\'){\n                    flag = false;\n                    break;\n                }\n            }\n            curr[0] = flag;\n            for(int j=1;j<=m;j++){\n                if(p[i-1] == s[j-1] || p[i-1] == \'?\'){\n                    curr[j] = prev[j-1];\n                }else if(p[i-1] == \'*\'){\n                    curr[j] = curr[j-1] || prev[j];\n                }else{\n                    curr[j] = false;\n                }\n            }\n            prev = curr;\n        }\n        return prev[m];\n    }\n```
['Two Pointers', 'String', 'C++']