Regular Expression Matching — 2D DP

Problem

Implement regex with . (any char) and * (0 or more of preceding).

Solutions

Python

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m,n=len(s),len(p)
        dp=[[False]*(n+1) for _ in range(m+1)]
        dp[0][0]=True
        for j in range(2,n+1):
            if p[j-1]=='*': dp[0][j]=dp[0][j-2]
        for i in range(1,m+1):
            for j in range(1,n+1):
                if p[j-1]=='*':
                    dp[i][j]=dp[i][j-2]  # zero occurrences
                    if p[j-2]=='.' or p[j-2]==s[i-1]:
                        dp[i][j]|=dp[i-1][j]  # one more occurrence
                elif p[j-1]=='.' or p[j-1]==s[i-1]:
                    dp[i][j]=dp[i-1][j-1]
        return dp[m][n]

Complexity

Time: O(mn) | Space: O(mn)