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


  • 1

    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

Log in to reply
 

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