My python solution using 68ms


  • 0
    R
    class Solution(object):
        def isMatch(self, s, p):
            """
            :type s: str
            :type p: str
            :rtype: bool
            """
            if not p and s:
                return False
            if not p and not s:
                return True
            indices=set([-1])
            np=len(p)
            for i in range(np-1):
                if p[i+1]!='*':
                    if p[i]=='.':
                        indices=set((j+1 for j in indices)) 
                    elif p[i]!='*':
                        indices=set((j+1 for j in indices if j+1<len(s) and s[j+1]==p[i]))
                else:
                    if not indices:
                        return False
                    elif p[i]=='.':    
                        indices=set(range(min(indices),len(s)))
                    else:
                        temp=set()
                        for j in indices:
                            temp.add(j)
                            j+=1
                            while j<len(s) and s[j]==p[i]:
                                temp.add(j)
                                j+=1
                        indices=temp
            if not indices:
                return False
            elif p[np-1]=='.' and len(s)-2 in indices:    
                return True
            elif p[np-1]=='*' and len(s)-1 in indices:
                return True
            elif p[np-1]!='.' and p[np-1]!='*' and len(s)-2 in indices and s[-1]==p[np-1]:
                return True
            else:
                return False

  • 0
    Z

    Can you explain your algorithm a bit? Thank you.


Log in to reply
 

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