Python DP solution in 36 ms

  • 8

    draw a table and use different test cases.
    After try and error, finally get AC.

    def isMatch(self, s, p):
        m = len(s)
        n = len(p)
        dp = [[True] + [False] * m]
        for i in xrange(n):
        for i in xrange(1, n + 1):
            x = p[i-1]
            if x == '*' and i > 1:
                dp[i][0] = dp[i-2][0]
            for j in xrange(1, m+1):
                if x == '*':
                    dp[i][j] = dp[i-2][j] or dp[i-1][j] or (dp[i-1][j-1] and p[i-2] == s[j-1]) or (dp[i][j-1] and p[i-2]=='.')
                elif x == '.' or x == s[j-1]:
                    dp[i][j] = dp[i-1][j-1]
        return dp[n][m]

  • 0

    @autekwing not sure how can you get 36ms when the first point in the runtime distribution graph is above 50ms...

    Anyway, this is an 8-liner that I just wrote, hope you like it!

    class Solution(object):
        def isMatch(self, s, p, memo={("",""):True}):
            if not p and s:      return False
            if not s and p:      return set(p[1::2]) == {"*"} and not (len(p) % 2)
            if (s,p) in memo:    return memo[s,p]
            char, exp, prev = s[-1], p[-1], 0 if len(p) < 2 else p[-2]
            memo[s,p] =\
                   (exp == '*' and ((prev in {char, '.'} and self.isMatch(s[:-1], p, memo)) or self.isMatch(s, p[:-2], memo)))\
                   (exp in {char, '.'} and self.isMatch(s[:-1], p[:-1], memo))
            return memo[s,p]
    # 445 / 445 test cases passed.
    # Status: Accepted
    # Runtime: 72 ms

  • 0

    If you try: s="baaaa" p="ba*", you will get 'false' with your solution.

  • 0

    @Coastchb It seems so.

Log in to reply

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