Recursion Brute force to top down DP and Bottom up
We can solve this problem using recursion. The basic conditions that we need to put here is when j reaches the end of pattern length, then we need to check if t
We can solve this problem using recursion. The basic conditions that we need to put here is when j reaches the end of pattern length, then we need to check if the i has also reached the end or not, if not then it will return false, otherwise true.\n\nIf the i reaches the end of the string i.e. i=s.length(), then only when p[j]=\' * \'  since * can be equal to the empty sequence as well. \n\nWe will now check if the current charcter of pattern and string are equal or not. They would be equal if either s[i]==p[j] or p[j]=\'?\'. \n\nif the current pattern character is \' * \' then we have two options either to move j forward and don\'t use it for matching or we can match and move the string index and keep the pattern index at j only. \n\nif the current character is not \' * \', then we need to check only if the first_match is true and move both the i and j index by 1.\n\n```\nclass Solution {\npublic:\n    bool isMatch(string s, string p) {\n        return helper(s,p,0,0);\n    }\n    \n    bool helper(string s, string p, int i, int j)\n    {\n        if(j==p.length())\n            return i==s.length();\n        if(i==s.length())\n            return (p[j]==\'*\' && helper(s,p,i,j+1));\n        bool first_match=(i<s.length() && (p[j]==s[i] || p[j]==\'?\'));\n        \n        if(p[j]==\'*\')\n        {\n            return (helper(s,p,i+1,j) || helper(s,p,i,j+1));\n        }\n        else\n        {\n            return (first_match && helper(s,p,i+1,j+1));\n        }\n    }\n};\n```\n\nTop down DP solution :\n\nWe are solving the same subproblems many times instead we can save those problems and resuse them. We can initialize the dp array with -1 so that if it becomes postive then that means it has been solved for that i and j. \n\n```\nclass Solution {\npublic:\n    bool isMatch(string s, string p) {\n        if(p.length()==0){\n            return (s.length()==0);\n        }\n        vector<vector<int>> v(s.length()+1,vector<int> (p.length()+1,-1));\n      return  helper(s,p,0,0,v);\n      \n    }\n    bool helper(string s, string p,int i,int j,vector<vector<int>> &v)\n    {\n        if(j==p.length())\n            return (i==s.length());\n        if(v[i][j]<0){\n        if(i==s.length())\n            v[i][j]= (p[j]==\'*\' && helper(s,p,i,j+1,v));\n        else if(i<s.length() &&  (p[j]==s[i] || p[j]==\'?\'))\n        {\n           v[i][j]=  helper(s,p,i+1,j+1,v);\n        }\n        \n        else if(p[j]==\'*\')\n        {\n            v[i][j]= (helper(s,p,i,j+1,v) || helper(s,p,i+1,j,v));\n        }\n        else\n        v[i][j]= false;\n        }\n        return v[i][j];\n    }\n};\n```\n\nBottom up solution\n\nWe can use bottom up approach to solve this problem. \n\ndp[0][0]=true or 1. it is because if the length of the pattern and matching string is 0 then, they are equal or they are a match.\n\nWe can fill the first row of the dp. First row of DP tells us that the matching string length is zero, then uptill which column the pattern matches the empty string. So we know that it can only happen if the pattern character at that point is \' * \' and if anything else comes other then a \' * \' then we break. \n\nNow, we can start filling the second row of dp, if the pattern is \' * \' at j-1, then either we can use it to match in that case it would be equal to dp[i-1][j] and if we use the empty string for \' * \' then it is equal to dp[i][j-1].\n\nIf the pattern at j-1 is not \' * \' then we need check if the characters are equal or pattern character at j-1 is \' ? \' then dp[i][j] =dp[i-1][j-1];\n\n```\nclass Solution {\npublic:\n    bool isMatch(string s, string p) {\n        if(p.length()==0)\n            return (s.length()==0);\n        vector<vector<int>> dp(s.length()+1,vector<int>(p.length()+1,0));\n        dp[0][0]=1;\n        for(int i=1;i<=p.length();i++)\n        {\n            if(p[i-1]==\'*\')\n                dp[0][i]=1;\n            else\n                break;\n        }\n        for(int i=1;i<=s.length();i++)\n        {\n            for(int j=1;j<=p.length();j++)\n            {\n                if(p[j-1]==\'*\')\n                {\n                    dp[i][j]=dp[i-1][j] || dp[i][j-1];\n                }\n                else if(p[j-1]==s[i-1] || p[j-1]==\'?\')\n                {\n                    dp[i][j]=dp[i-1][j-1];\n                }\n            }\n        }\n        return dp[s.length()][p.length()];\n      \n    }\n    \n};\n```
['Dynamic Programming', 'Recursion', 'C', 'C++']