[C++] Recursive | Memoized | DP | Explained
Logic: Explained as comments in recursive code.\nT.C of memoized and DP solution: O(NM). where N, M is length of string s and p.\n\n1. Recursive\n\n    bool isM
**Logic:** Explained as comments in recursive code.\nT.C of memoized and DP solution: O(NM). where N, M is length of string s and p.\n\n**1. Recursive**\n```\n    bool isMatch(string s, string p) {\n        int i=0, j=0;\n        \n        //i is pointer on s\n        //j is pointer on p\n        return fun(s,p,i,j);\n    }\n    \n    bool fun(string& s, string& p, int i, int j){\n        //1. Base case\n        //a. String p has ended - s must have ended for a match between them.\n        if(j==p.size()) return i == s.size();\n        \n        //b. String s has ended - p[j] could only be \'*\' or multiple \'*\' for a match.\n        if(i==s.size()) return (p[j] == \'*\' && fun(s,p,i,j+1));\n        \n        //2. If none of them has ended and p[j] is \'*\', nothing can be said before comparing rest of the strings, both of them.\n        if(p[j] == \'*\') return fun(s,p,i+1,j) || fun(s,p,i,j+1);\n        \n        //3. Else, when p[j] = \'?\' or a character - If it is a character it must be same as s[i]\n        else{\n            bool sameChar = i<s.size() && (p[j] == s[i] || p[j] == \'?\');\n            return (sameChar && fun(s,p,i+1,j+1));\n        }\n    }\n```\n\n**2. Memoized:** (Recursion + Storage)\n```\n\tbool isMatch(string s, string p) {\n        int i=0, j=0;\n        \n        //i is pointer on s\n        //j is pointer on p\n        int x = s.size(), y = p.size();\n        int t[2002][2002];\n        \n        for(int k=0; k<x+1; k++){\n            for(int m=0; m<y+1; m++){\n                t[k][m] = -1;\n            }\n        }\n        return fun(s,p,i,j, t);\n    }\n    \n    bool fun(string& s, string& p, int i, int j, int t[][2002]){\n        //1. Base case\n        //a. String p has ended - s must have ended for a match between them.\n        if(j==p.size()) return i == s.size();\n        \n\t\t//Check if result exists\n        if(t[i][j] != -1) return t[i][j];\n\t\t\n        //b. String s has ended - p[j] could only be \'*\' or multiple \'*\' for a match.\n        if(i==s.size()) return (p[j] == \'*\' && fun(s,p,i,j+1, t));\n        \n        \n        //2. If none of them has ended and p[j] is \'*\', nothing can be said before comparing rest of the strings, both of them.\n        if(p[j] == \'*\') {\n            t[i][j] = fun(s,p,i+1,j,t) || fun(s,p,i,j+1, t);\n            return t[i][j];\n        }\n        \n        //3. Else, when p[j] = \'?\' or a character - If it is a character it must be same as s[i]\n        else{\n            bool sameChar = i<s.size() && (p[j] == s[i] || p[j] == \'?\');\n            t[i][j] = (sameChar && fun(s,p,i+1,j+1, t));\n            return t[i][j];\n        }\n    }\n```\n\n**3. DP:** \n```\nbool isMatch(string& s, string& p) {\n        if(p.size()==0) return s.size() == 0;\n        \n        int x = s.size(), y = p.size();\n        vector<vector<int>> t(x+1, vector<int>(y+1,0));\n        \n        t[0][0] = 1;\n        \n        for(int i=1; i<=p.size(); i++){\n            if(p[i-1] == \'*\') t[0][i] = 1;\n            else break;\n        }\n        \n        for(int i=1; i<=s.size(); i++){\n            for(int j=1; j<=p.size(); j++){\n                if(p[j-1] == \'*\')  t[i][j] = t[i-1][j] || t[i][j-1];\n                else if(p[j-1] == \'?\' || p[j-1] == s[i-1]) {\n                    t[i][j] = t[i-1][j-1];\n                }\n            }\n        }\n        return t[x][y];\n    }\n```\n
['Dynamic Programming', 'Recursion', 'Memoization', 'C', 'C++']