10.md

10 Regular Expression Matching

Description

link

---

Solution

dp[i][j] : the ans of if p[:j] matches s[:i]

Recrusive :

• if p[j - 1] != '*' : dp[i][j] = dp[i - 1][j - 1] and (s[i - 1] == p[j - 1] or p[j - 1] == '.')
• else :
  • dp[i][j] = dp[i][j - 1] or dp[i][j - 2] # if * matches zero or one of the preceding element satisfied
  • dp[i][j] |= dp[i - 1][j] and (p[j - 2] == s[i - 1] or p[j - 2] == '.') # if the preceding element equals s[i - 1]

Initial : dp[0][i] = dp[0][i-2] and p[i - 1] == '*' for i in range(2, lenp + 1)

---

Code

Complexity T : O(mn) M : O(mn)

class Solution:
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        lenp = len(p)
        lens = len(s)
        
        dp = [[False] * (lenp + 1) for _ in range(lens + 1)]
        dp[0][0] = True
        
        for i in range(2, lenp + 1):
            dp[0][i] = dp[0][i-2] and p[i - 1] == '*'
        
        for i in range(1, lens + 1):
            for j in range(1, lenp + 1):
                if p[j - 1] != '*':
                    dp[i][j] = dp[i - 1][j - 1] and (s[i - 1] == p[j - 1] or p[j - 1] == '.')
                else:
                    dp[i][j] = dp[i][j - 1] or dp[i][j - 2] # if * matches zero or one of the preceding element satisfied
                    dp[i][j] |= dp[i - 1][j] and (p[j - 2] == s[i - 1] or p[j - 2] == '.') # if the preceding element equals s[i - 1]
        return dp[-1][-1]