Python Iterative solution beats 98%


  • 0
    A
    class Solution(object):
        def shorten(self, p):
            i, last, lasti, lp = 0, None, -1, len(p)
            ps = ''
            while i < lp:
                if i + 1 < lp and p[i+1] == '*':
                    if last == None:
                        last, lasti = p[i], i
                        ps += p[i] + p[i + 1]
                    else:
                        if (last == p[i] or last == '.') and i - lasti == 2:
                            lasti += 2
                        else:
                            last, lasti = p[i], i
                            ps += p[i] + p[i + 1]
                    i += 2
                else:
                    ps += p[i]
                    i += 1
                    last, lasti = None, - 1
            
                if debug: print ps
            return ps
            
        def isMatch(self, s, p):
            """
            :type s: str
            :type p: str
            :rtype: bool
            """
            p = self.shorten(p)
            ls, lp = len(s), len(p)
            if lp == 0 and ls > 0: return False
            if lp == 0 and ls == 0: return True
            stac = []
            i, j = 0, 0
            while i < ls:
                if j < lp - 1 and p[j + 1] == '*':
                    stac.append( (p[j], j + 1, i) )
                    j += 2
                elif j < lp and (p[j] == '.' or p[j] == s[i]):
                    i += 1
                    j += 1
                elif len(stac) > 0:
                    sc, sdx, idx = stac[-1]
                    stac = stac[:-1]
                    i = idx
                    if sc == '.' or s[i] == sc:
                        i += 1
                        stac.append((sc, sdx, i))
                    j = sdx + 1
                else: return False
            
            while j + 1 < lp and p[j + 1] == '*': j += 2
            return j == lp
    

Log in to reply
 

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