Python two pointer solution with explanation. (beat ~60%)

• I tried different solutions for this problem.

Typical DP: It uses O(mn) memory and searches all the possible paths O(mn) which is redundant, which fails TLE or MLE. We can use a one-dimensional array to save the memory.

Two pointers: Actually it is just a concise version of DP. We use two pointers i and j to record the current matching progress and a 'next_try' variable to store the next starting points. We update 'next_try' when we meet a new '*' so this is a greedy algorithm. Once we failed in matching them, we go to the 'next_try' and try from that position until we use up 'next_try'.

Hope it helps you.

class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""

``````    # i and j are the pointers to the char that we are going to check,
# if i and j reach their ends simultaneously, the two strings are matched.

# next_try stores a position(coordinates) to record the position of last star
# (plus one, so that it can be the 'next' 'try') and corresponding j.

# next_try can be seen as another possible starting point to check the two strings.
# next_try is updated when we meet a new '*'. We only care about the last '*' because
# the last '*' means that we have already matched as much as we can for p and the last
# '*' can cover any string so we can throw away the previous next_try values and start
# from here. We're greedy.

i, j, next_try =  0, 0, None

while 1:

# Quick judge by length of string: if len(p w/o '*') is bigger than len(s), return False
if len(p)-p.count('*')>len(s):
return False

# check if i outbounds p
if i >= len(p):
# both i and j reaches end of their strings simultaneously
if j >= len(s):
return True
# go to next_try
if next_try:
i, j = next_try
if j>=len(s):
# no more try
return False
else:
j+=1
next_try = [i,j]
else:
# if there is no next_try (None), return False
return False
else:
# check if '*'
if p[i] != '*':
# not '*', we compare the two chars if exist else return False
if j>=len(s):
# see if there is next_try (update it first)
if next_try:
i, j = next_try
if j>=len(s):
# cannot update next_try since it's over limit
return False
else:
j+=1
next_try = [i,j]
else:
# if not next_try available, return False
return False
else:
# j<len(s), we can compare the two chars
if (p[i]=='?') or (p[i]==s[j]):
i+=1
j+=1
else:
# if chars are not equal, we need to test next_try (update it first)
if next_try:
next_try=[next_try[0],next_try[1]+1]
i, j = next_try
else:
# if not next_try available, return False
return False
else:
# '*', we need to update branch coordinates for next_try
next_try = [i+1, j]
i, j = next_try``````

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