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


  • 0
    S

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

Log in to reply
 

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