python dp solution


  • 1
    R
    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]
                    else:
                        T[i][j]  = False
                        
            return T[i][j]
    
    

  • 0
    D

    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
    R

    @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
    D

    @ruhao

    got it, thanks


Log in to reply
 

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