Python code using 2D dynamic programming


  • 0
    H
    class Solution(object):
        def isMatch(self, s, p):
            """
            :type s: str
            :type p: str
            :rtype: bool
            """
            n, m = len(s), len(p)
            match = [[False for j in range(m+1)] for i in range(n+1)]
            match[0][0] = True
            # in case s == ''
            for j in range(m):
                if p[j] == '*':
                    match[0][j+1] = match[0][j]
            # fill 'match'
            for i in range(n):
                for j in range(m):
                    if p[j] == '?':
                        match[i+1][j+1] = match[i][j]
                    elif p[j] == s[i]:
                        match[i+1][j+1] = match[i][j]
                    elif p[j] == '*':
                        match[i+1][j+1] = match[i+1][j] or match[i][j+1] # '*' can match any string
                        
            return match[n][m]
    

Log in to reply
 

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