# "two pointers", python, recursive, with rigorous proof

• 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).
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.