🚀 ✅ Detailed explaination 🔥 with Pictures ✅ 🔥 🚀 in C++,Java , Python , DP top down tabulation.
Approach\n- Here the Approach is literally same as the sum https://leetcode.com/problems/regular-expression-matching/ or a small improvisation of it here the \'
# Approach\n- Here the Approach is literally same as the sum [https://leetcode.com/problems/regular-expression-matching/]() or a small improvisation of it here the \'*\' symbol can take any pattern that is the only difference between those two, below is the pictorical representation of the approach followed and the breifing of it is given below.\n\n- ![pic1.png](https://assets.leetcode.com/users/images/20f32b02-f04f-4d07-a667-a47e38e0fe02_1681159815.5575788.png)\n\n>- Here we can clearly see that the final DP table is completely dependent on its previous states $i.e$ given by the expression as follows -\n`dp[i][j] = dp[i-1][j] | dp[i][j-1] | dp[i-1][j-1] ` when `p[j-1]` is\nindicated by a \'*\' otherwise we go with `dp[i-1][j-1]` as the state transition. \n\n>- This would be the way in which we must proceed based and the prev state and the final answer would be `dp[m][n]` we always do a step down indexing for convineance purposes.\n\n---\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    bool isMatch(string s, string p) {\n    int n=s.length();\n        int m=p.length();\n        bool res[m+1][n+1];\n        memset(res,false,sizeof(res));\n        res[0][0]=true;\n        for(int i=1;i<=m;i++){\n            if(p[i-1]==\'*\'){\n                res[i][0]=res[i-1][0];\n            }\n            for(int j=1;j<=n;j++){\n                if(p[i-1]==\'*\'){\n                    res[i][j]=res[i-1][j]||res[i][j-1];\n                }\n                else if(p[i-1]==s[j-1]||\'?\'==p[i-1]){\n                    res[i][j]=res[i-1][j-1];\n                }\n            }\n        }\n        return res[m][n];\n    }   \n};\n```\n```Java []\nclass Solution {\n    public boolean isMatch(String s, String p) {\n        int sIndex = 0, pIndex = 0, matchIndex = 0, starIndex = -1;\n        \n        while (sIndex < s.length()) {\n            if (pIndex < p.length() && (s.charAt(sIndex) == p.charAt(pIndex) || p.charAt(pIndex) == \'?\')) {\n                sIndex++;\n                pIndex++;\n            } else if (pIndex < p.length() && p.charAt(pIndex) == \'*\') {\n                starIndex = pIndex;\n                matchIndex = sIndex;\n                pIndex++;\n            } else if (starIndex != -1) {\n                pIndex = starIndex + 1;\n                matchIndex++;\n                sIndex = matchIndex;\n            } else {\n                return false;\n            }\n        }\n        \n        while (pIndex < p.length() && p.charAt(pIndex) == \'*\') {\n            pIndex++;\n        }\n        \n        return pIndex == p.length();\n    }\n}\n```\n```Python []\nclass Solution:\n    def isMatch(self, s: str, p: str) -> bool:\n        s_len, p_len, p_idx, s_idx, p_star, s_backtrack = len(s), len(p), 0, 0, -1, -1\n        \n        while s_idx < s_len:\n            if p_idx < p_len and p[p_idx] in [\'?\', s[s_idx]]:\n                p_idx += 1\n                s_idx += 1\n            elif p_idx < p_len and p[p_idx] == \'*\':\n                p_star = p_idx\n                s_backtrack = s_idx\n                p_idx += 1\n            else: #elif p_idx == p_len or p[p_idx] != s[s_idx]:\n                if p_star == -1:\n                    return False\n                else:\n                    #backtrack\n                    p_idx = p_star + 1\n                    s_idx = s_backtrack + 1\n                    s_backtrack = s_idx\n\n        return all(p[idx] == \'*\' for idx in range(p_idx, p_len))\n```\n---\n# Complexity\n>- Time complexity: Here the complexity would be $O(n^2)$ as we can see that we need a 2d looping for the management of memoization using the length so $O(n^2)$.\n\n>- Space complexity: Here We can clearly see that we need a 2D dp so the space complexity will also be $O(n^2)$ and which can be further optimised to $O(n)$ by using space optimisation in Dp as the final states and previous states differ by one index.\n\n\n---\n\nIF YOU LIKE THE SOLUTION THEN PLEASE UPVOTE MY SOLUTION BECAUSE IT GIVES ME MOTIVATION TO REGULARLY POST THE SOLUTION.\n\n![UPVOTE.jpg](https://assets.leetcode.com/users/images/0ba8ee63-53aa-40f7-994a-663b1bc3c77f_1681159079.630099.jpeg)\n
['Dynamic Programming', 'Recursion', 'Python', 'C++', 'Java']