4 Approaches ||  Recursion || Memoization || Tabulation || Space-Optimized Solution
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem involves checking if a given string s matches a pattern p where the pattern
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem involves checking if a given string s matches a pattern p where the pattern may include wildcard characters:\n\n- ? matches any single character.\n- ( * ) matches any sequence of characters (including an empty sequence).\nTo solve this problem, we use dynamic programming to build up the solution based on subproblems. We consider various ways to match parts of the string with parts of the pattern using wildcard characters.\n\n# Approach 1: Recursion\n<!-- Describe your approach to solving the problem. -->\n- This approach solves the problem by breaking it down into smaller subproblems, but it doesn\'t optimize for repeated calculations, which can lead to inefficiencies for large inputs.\n\n# Complexity\n- Time complexity: O(n*m)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n*m)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\nprivate:\n    bool solve(string &s,string &p,int i,int j)\n    {\n        //base case\n        if(i==0 && j==0) return true;\n\n        if(i>0 && j==0) return false;\n\n        if(i==0 && j>0)\n        {\n            for(int k=1;k<=j;k++)\n            {\n                if(p[k-1]!=\'*\') return false;\n            }\n            return true;\n        }\n\n            //match\n            if(s[i-1]==p[j-1] || p[j-1]==\'?\') return solve(s,p,i-1,j-1);\n            else if(p[j-1]==\'*\') \n                return ( solve(s,p,i-1,j)|| solve(s,p,i,j-1));\n            else return false;\n    }\n\npublic:\n    bool isMatch(string s, string p) {\n         return solve(s,p,s.length(),p.length());\n    }\n};\n```\n# Approach 2: Memoization\n<!-- Describe your approach to solving the problem. -->\n- This approach improves efficiency by storing the results of previously computed subproblems in a table (dp). This avoids redundant calculations and speeds up the solution, especially for larger inputs.\n\n# Complexity\n- Time complexity: O(n*m)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n*m)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\nprivate:\n    bool solveMem(string &s,string &p,int i,int j,vector<vector<int>> &dp)\n    {\n        //base case\n        if(i==0 && j==0) return true;\n\n        if(i>0 && j==0) return false;\n\n        if(i==0 && j>0)\n        {\n            for(int k=1;k<=j;k++)\n            {\n                if(p[k-1]!=\'*\') return false;\n            }\n            return true;\n        }\n\n        if(dp[i][j]!=-1) return dp[i][j];\n\n        //match\n        if(s[i-1]==p[j-1] || p[j-1]==\'?\')  return dp[i][j]=solveMem(s,p,i-1,j-1,dp);\n        else if(p[j-1]==\'*\') \n            return dp[i][j]=( solveMem(s,p,i-1,j,dp)|| solveMem(s,p,i,j-1,dp));\n        else return false;\n    }    \n\npublic:\n    bool isMatch(string s, string p) {\n\n         int n=s.length();\n         int m=p.length();\n\n         vector<vector<int>> dp(n+1,vector<int> (m+1,-1));\n         return solveMem(s,p,n,m,dp);\n\n};\n```\n# Approach 3: Tabulation\n<!-- Describe your approach to solving the problem. -->\n- Create a 2D DP table where dp[i][j] represents if the first i characters of the string s match the first j characters of the pattern p.\n- Use this table to iteratively fill in values based on whether characters match or if the pattern contains wildcards (? or *).\n\n# Complexity\n- Time complexity: O(n*m)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n*m)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\nprivate:\n    bool solveTab(string s,string p)\n    {\n        int n=s.length();\n        int m=p.length();\n        vector<vector<int>> dp(n+1,vector<int> (m+1,0));\n        dp[0][0]=true;\n\n        for(int j=1;j<=m;j++)\n        {\n            bool flag=true;\n            for(int k=1;k<=j;k++)\n            {\n                if(p[k-1]!=\'*\')\n                {\n                    flag=false;\n                    break;\n                }\n            }\n            dp[0][j]=flag;\n        }\n\n        for(int i=1;i<=n;i++)\n        {\n            for(int j=1;j<=m;j++)\n            {\n                //match\n                if(s[i-1]==p[j-1] || p[j-1]==\'?\')  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\n        return dp[n][m];\n    }\npublic:\n    bool isMatch(string s, string p) {\n\n         return solveTab(s,p);\n\n    }\n};\n```\n# Approach 4: Space Optimization\n<!-- Describe your approach to solving the problem. -->\nReduce space complexity by using a rolling array technique where we keep only the current and previous rows of the DP table instead of the full table.\n\n# Complexity\n- Time complexity: O(n\xD7m)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(m)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\nprivate:\n    bool solveSO(string s,string p)\n    {\n        int n=s.length();\n        int m=p.length();\n        vector<int> prev(m+1,0);\n        vector<int> curr(m+1,0);\n        \n        prev[0]=true;\n\n        for(int j=1;j<=m;j++)\n        {\n            bool flag=true;\n            for(int k=1;k<=j;k++)\n            {\n                if(p[k-1]!=\'*\')\n                {\n                    flag=false;\n                    break;\n                }\n            }\n            prev[j]=flag;\n        }\n\n        for(int i=1;i<=n;i++)\n        {\n            for(int j=1;j<=m;j++)\n            {\n                //match\n                if(s[i-1]==p[j-1] || p[j-1]==\'?\')  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\n        return prev[m];\n    }     \npublic:\n    bool isMatch(string s, string p) {\n        return solveSO(s,p);\n    }\n};\n``` \n![upvote.jpg](https://assets.leetcode.com/users/images/59dec2d2-bcf8-462c-990d-5b61cb78c3a2_1725752865.5187407.jpeg)\n
['String', 'Dynamic Programming', 'Recursion', 'Memoization', 'C++']