Python AC solution beats 94.18%


  • 0
    M

    Details to how DP works is already covered in great detail in other posts and I shan't repeat them here.

    Key to my solution:

    I split the pattern string into 2 arrays, this facilitates the ready reuse of solution in wildcard matching without considering much for s[j-2] due to presence of * characters. (yes I'm lazy)

    "a*.bc*d*" -> [ 'a' , '.' , 'b' , 'c' , 'd' ] , [ True, False, False, True, True ]

    What modifications from wildcard matching is needed:

    • DP array initialization (since any non * character can be nullified with a following *)
    • Evaluation for each cell (just some additional booleans with AND)
    • ? to .

    That's all the needed stuff. (REALLY!)

    What's not needed though, is some lines to print the DP array (commented with #) for your reference

    class Solution(object):
        def isMatch(self, s, p):
            #def pbol(boo,t="T",f=" "):
            #    return t if boo else f
            if not p:
                return not s
            
            p2 = [ch for ch in p if ch!='*']
            p3 = [(p[i+1]=='*') for i,val in enumerate(p[:-1]) if val!='*']
            if p[-1]!='*':
                p3.append(False)
            
            dp=[[False for _ in range(len(s)+1)] for _ in range(len(p2)+1)]
            
            t=0
            for boo in p3:
                if boo:
                    t+=1
                else:
                    break
            for i in range(t+1):
                dp[i][0]=True
            
            for i in range(len(p2)):
                for j in range(len(s)):
                    if (not p3[i]) and (p2[i]=='.' or p2[i]==s[j]):
                        dp[i+1][j+1]=dp[i][j]
                    if p3[i]:
                        dp[i+1][j+1]=dp[i][j+1] or (dp[i+1][j] and (p2[i]=='.' or p2[i]==s[j]))
            #print("\t {}".format(s))
            #for i in range(len(p2)+1):
            #    print("{}{}\t{}".format( pbol(i,p2[i-1],""), pbol(i,pbol(p3[i-1]),""), "".join(pbol(bol) for bol in dp[i]) ))
            return dp[len(p2)][len(s)]
    

    P.S. Above is my first submitted and accepted solution. Attempting to optimize it by caching the least possible j value gave me a WA submission and turns out performing EXACTLY the same. Micro-optimization is the root of all evil :(

    class Solution(object):
        def isMatch(self, s, p):
            """
            :type s: str
            :type p: str
            :rtype: bool
            """
            #rewrite with DP
            #simplify string
            #def pbol(boo,t="T",f=" "):
            #    return t if boo else f
            if not p:
                return not s
            
            p2 = [ch for ch in p if ch!='*']
            p3 = [(p[i+1]=='*') for i,val in enumerate(p[:-1]) if val!='*']
            if p[-1]!='*':
                p3.append(False)
            
            #PS
            dp=[[False for _ in range(len(s)+1)] for _ in range(len(p2)+1)]
            
            t=0
            for boo in p3:
                if boo:
                    t+=1
                else:
                    break
            for i in range(t+1):
                dp[i][0]=True
            
            t2=0
            #print("\n\t {}".format(s))
            #print("\t{} {}".format("".join(pbol(bol) for bol in dp[0]), t))
            for i in range(len(p2)):
                buf = False
                for j in range(t2,len(s)):
                    if (not p3[i]) and (p2[i]=='.' or p2[i]==s[j]):
                        dp[i+1][j+1]=dp[i][j]
                    if p3[i]:
                        dp[i+1][j+1]=dp[i][j+1] or (dp[i+1][j] and (p2[i]=='.' or p2[i]==s[j]))
                    if not buf and dp[i+1][j+1]:
                        buf = True
                    if i>=t and not buf:
                        t2+=1
                #print("{}{}\t{} {}".format(p2[i], pbol(p3[i]), "".join(pbol(bol) for bol in dp[i+1]), t))
            return dp[len(p2)][len(s)]
    

Log in to reply
 

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