0010 - Regular Expression Matching

[rajapuranam]

Description of the Problem

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*' where:

'.' Matches any single character.​​​​
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).

Example 1:
Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:
Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Code

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        string, pattern = [], []
        string[:0], pattern[:0] = s, p
        string.insert(0, 0) 
        pattern.insert(0, 0)
        s, p = len(string), len(pattern)
        dp = [[False for _ in range(p)] for __ in range(s)]
        dp[0][0] = True
        for i in range(p):
            if pattern[i] is '*' and dp[0][i-2]: dp[0][i] = True 
        for i in range(1, s):
            for j in range(1, p):
                if pattern[j] is string[i] or pattern[j] is '.':
                    dp[i][j] = dp[i-1][j-1]
                elif pattern[j] is '*' and (pattern[j-1] is string[i] or pattern[j-1] is '.'):
                    dp[i][j] = dp[i][j-2] or dp[i-1][j]
                elif pattern[j] is '*' and not (pattern[j-1] is string[i] or pattern[j-1] is '.'):
                    dp[i][j] = dp[i][j-2]
        return dp[s-1][p-1]

Link To The LeetCode Problem

LeetCode

[rajapuranam]

Please assign this issue to me.