The following algorithm is not new. It is just a recursive implementation of this. The key contribution is a proof of why this works. More precisely, why we only need to move back to the previous * location. The proof is after the script.

```
def isMatch(self, s, t):
return self.helper(list(s), list(t), 0, 0, 0, -1)
def helper(self, s, t, i, j, pos, pot):
if i >= len(s) and j >= len(t):
return True
if i >= len(s):
if t[j] != '*':
return False
return self.helper(s, t, i, j + 1, pos, pot)
if j >= len(t):
if pot == -1:
return False
return self.helper(s, t, pos, pot + 1, pos + 1, pot)
if t[j] == '*':
return self.helper(s, t, i, j + 1, i, j)
if s[i] == t[j] or t[j] == '?':
return self.helper(s, t, i + 1, j + 1, pos, pot)
if pot == -1:
return False
return self.helper(s, t, pos, pot + 1, pos + 1, pot)
```

The hard part is to understand the line

```
if t[j] == '*':
return self.helper(s, t, i, j + 1, i, j)
```

```
let a, b, c, d be strings.
s = a + b
p = c + '*' + d
I will use ~ for match
claim: Suppose using the process we get the step c ~ a. Then s ~ p if and only if b ~ '*' + d.
proof: suppose s ~ p, then there are two cases:
case 1: a = a1 + a2, c ~ a1, and a2 + b ~ '*' + d.
The fact that even though c ~ a1 we still reached the step c ~ a implies that a2 does not match the front part of d.
But because a2 + b ~ '*' + d, we know a2 is matched by '*'. This implies b ~ '*' + d.
case 2: b = b1 + b2, a + b1 ~ c, b2 ~ '*' + d.
This is the easy case. '*' + d ~ '*' + '*' + d ~ '*' + b2 ~ b1 + b2 = b. (clearly ~ is transitive).
```