✨💯💥Linear Time Solution | Detailed Explanation | Images | Visualisations💥💯✨
Intuition\nI solved this problem using dynamic programming .Its time complexity was O(len(s)len(p)). However this post doesn\'t explain that solution. I am sure
# Intuition\nI solved this problem using dynamic programming .Its time complexity was $$O(len(s)*len(p))$$. However this post doesn\'t explain that solution. I am sure there are many more posts to explain that.\n\nThereafter I found a solution in linear time using 2 pointer approach. I have made some visualisations using python to understand this solution. Here is the link to the blog post for this solution by [Yu](https://yucoding.blogspot.com/2013/02/leetcode-question-123-wildcard-matching.html):\n\n---\n\n\n\n# Approach\n1. Start by setting up some placeholders: We set up some variables that keep track of positions and states (s_cur, p_cur, match, star) as we move through the string and pattern.\n2. (Loop) While we haven\'t reached the end of the string, we check the following:\n    1. If the current character in the pattern matches the current character in the string or if the pattern character is a question mark, we move forward in both the string and pattern.\n    1. If we encounter a \'*\' in the pattern, we note down the current positions in the string and pattern and move the pattern position forward.\n    1. If none of the above conditions are met, but we have seen a \'\' before, we reset the pattern position after the \'\' to the next character, increment the match counter, and move the string position to the new match.\n    1. If none of the conditions are met mainly (p_cur reaches the end) and we have no \'*\' to fall back on, we know the pattern doesn\'t match the string, so we return False.\n3. After going through the string, we check if there are any \'*\' characters left in the pattern. If there are, we move the pattern position forward.\n4. Finally, if we\'ve reached the end of the pattern at this point, we know the pattern matches the string, so we return True. Otherwise, we return False.\n<!-- Describe your approach to solving the problem. -->\n\n---\n\n\n# Complexity\n- Average Time complexity: $$O(n)$$\n- Worst Case Time complexity: $$O(mn)$$ (Eg String (s): "aaaaaaaaaaab"\nPattern (p): "*aab")\n- Space complexity: $$O(1)$$\n\n\n---\n\n\n# Dry Run with Visualisation \nThe yellow highlighted cells represent s_cur and p_cur respectively\n$$\ns =\nabcabczzzde\n$$\n$$\np =\n*abc???de*\n$$\n\n![pointer_movement_visualization.gif](https://assets.leetcode.com/users/images/4f0fbee5-91d8-44ee-9f23-7ae7d562ca37_1699066595.5983377.gif)\n\nWorst Case Example\n$$\ns =\naaaaaaab\n$$\n$$\np =\n*aab\n$$\n![pointer_movement_visualization2.gif](https://assets.leetcode.com/users/images/ae014f02-b52e-445d-ada2-a367243f8846_1699068400.8442802.gif)\n$$\ns =\nabxbcbgh\n$$\n$$\np =\na*c*h\n$$\n![pointer_movement_visualization3.gif](https://assets.leetcode.com/users/images/b714383c-c690-47b0-b2b3-a09b6039d556_1699069692.372215.gif)\n\n\n\n---\n\n\n\n# Code\n```\nclass Solution:\n    def isMatch(self, s, p):\n        s_cur = 0\n        p_cur= 0\n        match = 0\n        star = -1\n        while s_cur<len(s):\n            if p_cur<len(p):\n                print("Pattern Char",p[p_cur])\n            if p_cur< len(p) and (s[s_cur]==p[p_cur] or p[p_cur]==\'?\'):\n                s_cur = s_cur + 1\n                p_cur = p_cur + 1\n            elif p_cur<len(p) and p[p_cur]==\'*\':\n                match = s_cur\n                star = p_cur\n                p_cur = p_cur+1\n            elif (star!=-1):\n                p_cur = star+1\n                match = match+1\n                s_cur = match\n            else:\n                return False\n        while p_cur<len(p) and p[p_cur]==\'*\':\n            p_cur = p_cur+1\n            \n        if p_cur==len(p):\n            return True\n        else:\n            return False\n```\n\n---\n\nAll suggestions are welcome.\nIf you have any query or suggestion please comment below.\nPlease upvote\uD83D\uDC4D if you like\uD83D\uDC97 it. Thank you:-)\nHappy Learning, Cheers Guys \uD83D\uDE0A\nKeep Grinding \uD83D\uDE00\uD83D\uDE00\n
['Two Pointers', 'String', 'Dynamic Programming', 'Recursion', 'Python3']