Finite-state machine with Python & dictionary. 13 lines, O(p+s) time
python\nclass Solution(object):\n    def isMatch(self, s, p):\n        """\n        :type s: str\n        :type p: str\n        :rtype: bool\n        """\n     
```python\nclass Solution(object):\n    def isMatch(self, s, p):\n        """\n        :type s: str\n        :type p: str\n        :rtype: bool\n        """\n        transfer = {}\n        state = 0\n        \n        for char in p:\n            if char == \'*\':\n                transfer[state, char] = state\n            else:\n                transfer[state, char] = state + 1\n                state += 1\n        \n        accept = state\n        states = {0}\n        \n        for char in s:\n            states = {transfer.get((at, token)) for at in states if at is not None for token in (char, \'*\', \'?\')}\n        \n        return accept in states\n```\n\nAbout finite-state machine: https://en.wikipedia.org/wiki/Finite-state_machine\n\nThe string pattern matching can be seen as running a FSM. For example, you can use the following FSM to represent pattern `a*c?b`. \nYou always start at state 0, and take each character of `s` as a "token". When a token matches the label on a link, you can transfer from one state to another via that link. `*` and `?` are special tokens that can match any token, or in other words, you can always transfer via a `*` or `?` link regardless of what token is fed from `s`. At the end, if you reach the final state, called the accepting state (state 4 in our example), that means you\'ve got a match. \n`*` and `?` are slightly different: `?` can match only 1 character, which means after you transfer via a `?` link, you can\'t traverse it again, but after you transfer via a `*` link, you still have access to it, infinitely. This is why a `?` link takes you to a new state, while a `*` link takes you back to where it starts, thus this link can be traversed infinitely.\nDue to the behavior of `*` links, you may have access to multiple states from a certain state. E.g. at state 1 below, with a token `c` you can transfer via the `c` link and arrive at 2, or transfer via the `*` link to arrive back at state 1. As a result, you can be at multiple states simultenaously (think of parallel universes). Among all the states you "can be at", you only need one of them being the accepting state to conclude a successful match.\n\n![image](https://s3-lc-upload.s3.amazonaws.com/users/guozhenli/image_1529467714.png)\n\nThe first `for` loop builds up a FSM from `p`. The states of the machine are labeled as 0, 1, 2, ... The last state reached during the FSM building is the accepting state.\n\nThe second `for` loop scans string `s` and run the FSM, by tracking what `states` the machine is at, and what `token` is read from `s`. The `*` and `?` tokens are always available. Because you can be at multiple states at the same time, in the second loop the `states` variable is a set of integers, rather than a single integer.\n\nFinally, if any of the state the FSM has reached matches the accepting state, we can conclude `s` and `p` match, otherwise they don\'t match.\n\n\n\nThe first loop (FSM building) takes O(p) time. The second loop (string scanning) iterates over `s` once, thus O(s) iterations. Overall there are O(p+s) iterations. However, more strictly speaking in each iteration of the `for char in s` loop, you also iterate through all states you may be at (`for at in states`), which can be as many interations as the number of `*`\'s in `p`, which is bounded by p. Thus the overall complexity in worst case is O(p+sp). If you believe the number of `*`\'s in `p` can be bounded by a constant, then the overall complexity can be reduced to O(p+s).\n\nThe FSM diagram was drawn with [Finite State Machine Designer - by Evan Wallace](http://madebyevan.com/fsm/).\n\n**[Update 2020-02-08]**\n\nThanks to the very insightful comments from @ericauld , I\'m realizing the connections between the FSM solution and DP solutions. I really like this finding so I\'m happily writing it down with some visualization.\n\nQuote @ericauld\n> it\'s nice to think of it as a decision tree with nodes corresponding to pairs (state, location in s). That leaves the approach open to different types of solutions, and makes the problem more clear. We can traverse this decision tree in breadth-first fashion, as you do, or in depth-first fashion, as other solutions do. I think saying "you can be in multiple states at the same time" obscures what\'s really going on and is confusing. Thanks for helping me think of the problem more clearly.\n\nTo visualize this, imagine matching string `acccb` with pattern `a*c?b` again. The FSM is set up the same as above, and your journey down the path will look like this:\n![image](https://assets.leetcode.com/users/guozhenli/image_1581232923.png)\nEach node in this diagram means <state in FSM, substring matched so far>. Starting at 0, where your only choice with string token \'a\' is to match with \'a\' in pattern, and arrive at state 1. At state 1, you have the next token in `s` -- \'c\' to work with, and your choices are to mathch it with \'\\*\' thus circle back to state 1 (the \'c=\\*\' arrow), or to match \'c\' of `s` with \'c\' of `p` and go to state 2 (the \'c=c\' arrow). In either case, you\'ve matched \'ac\' so far. Keep doing this, when you\'ve used all tokens in `s` you\'re at the leaves to the right-most side, and the states you could be at are {1, 3, 4}, which is actually the final value of `states` at `return` time in my code above. Among these states, 4 is an accepting state, so we return `True`.\n\nNow that nodes in the same column/depth of this decision tree have the same "substring matched so far" value, bring them up to top, make a row for each state, and mark every valid node with a "T", we get:\n|   | \'\' | a | ac | acc | accc | acccb |\n|---|----|---|----|-----|------|-------|\n| 0 | T  |   |    |     |      |       |\n| 1 |    | T | T  | T   | T    | T     |\n| 2 |    |   | T  | T   | T    |       |\n| 3 |    |   |    | T   | T    | T     |\n| 4 |    |   |    |     |      | T     |\n\nHere you go the DP table! Other DP solutions essentially fill this table row-by-row from top down (DFS), and the FSM solution essentially fills it column-by-column from left to right (BFS).\n\n**[Update 2020-07-08]**\nA few slight changes to squeeze some performance:\nThe line `states = ...` changed from\n```python\nstates = set([transfer.get((at, token)) for at in states for token in [char, \'*\', \'?\']])\n```\nto\n```python\nstates = {transfer.get((at, token)) for at in states if at is not None for token in (char, \'*\', \'?\')}\n```\n\n3 things happened here:\n1. `set([...])` to `{...}` -- to avoid creating a list before converting it to a set; instead, construct a set directly\n2. `for at in states` to `for at in states if at is not None` -- to avoid executing `transfer.get((None, token))`, which we know is not any useful, potentially many times. (Thanks to comment from @Xyzzy123 for pointing out this inefficiency.)\n3. `token in [char, \'*\', \'?\']` to `for token in (char, \'*\', \'?\')` -- because [constructing a tuple is faster than cosntructing a list](https://stackoverflow.com/questions/3340539/why-is-tuple-faster-than-list-in-python)
[]