python dp solution

  • 1
    class Solution(object):
        def isMatch(self, s, p):
            :type s: str
            :type p: str
            :rtype: bool
            if s == p:
                return True
            # INITIALIZING
            # 2
            m = len(s)
            # 1
            n = len(p)
            T = [[False for j in range(n+1)] for i in range(m+1)]
            T[0][0] = True
            #  Deals with patterns like a* or a*b* or a*b*c*
            for i in range(1, n+1):
                if p[i-1] == '*':
                    T[0][i] = T[0][i-2]
            if not s:
                return T[-1][-1]
            s = " "+s
            p = " "+p
            for i in range(1, m+1):
                for j in range(1, n+1):
                    if s[i] == p[j] or p[j] == '.':
                        T[i][j] = T[i-1][j-1]
                    elif p[j] == '*':
                        if j > 1:
                            T[i][j] = T[i][j-2]
                        if s[i] == p[j-1] or p[j-1] == '.':
                            T[i][j] = T[i][j] or T[i-1][j]
                        T[i][j]  = False
            return T[i][j]

  • 0

    could you explain the logic behind this please? I am trying to understand but I am having trouble.

    what does T[i][j] represent?

    if you have a "*", why do you do T[i][j] = T[i][j-2]?

  • 0

    @dal Hi,
    boolean in T[i][j] represents if string[:i] and pattern[:j] is a match. (note I had a empty space appended to the front of both s (string) and p (pattern) so the index is adjusted)

    in the case of p[j] == "*", we check T[i][j] = T[i][j-2] to see if pattern[j-1:j+1] could match an empty string.

  • 0


    got it, thanks

Log in to reply

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