Regular Expression Matching Leetcode Python Solution

LeetCode has a Medium coding Problem in Its’ Algorithm Section “Regular Expression Matching Leetcode Python”. Today We are going to solve this problem. LeetCode Link of the Problem is HERE.

Question

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).

Examples

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

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".

Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Constraints:

• 1 <= s.length <= 20
• 1 <= p.length <= 30
• s contains only lowercase English letters.
• p contains only lowercase English letters, '.', and '*'.
• It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.

Solution to Regular Expression Matching Leetcode Python

The Skeleton code given in Leetcode Python is

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """

Firstly, check for the base condition. Suppose that a given input string is empty and the pattern is also empty then the function must return True. And if the String is nonempty but the Pattern is empty then the function must return False.

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        rows = len(s)
        columns = len(p)
        if (len_Str == 0 and len_pattern == 0):
            return True
        if (len_pattern == 0):
            return False

Secondly, Create a boolean 2D dp array with sizes as boolean[][] dp = new boolean[s.length() + 1][p.length() + 1]. We’ve added an additional 1 to account for the possibility that one or both of the strings are empty.It’s a match if both strings are empty, therefore dp[0][0] = true.

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        rows = len(s)
        columns = len(p)
        if (len_Str == 0 and len_pattern == 0):
            return True
        if (len_pattern == 0):
            return False        
        dp = [[False for j in range(columns + 1)] for i in range(rows + 1)]
        # Since empty string and empty pattern are a match
        # print(dp)
        dp[0][0] = True

Let’s state s[i – 1] == p[j – 1] for non-empty strings, which indicates the I – 1)th and (j – 1)th characters are the same. This implies we must determine whether or not the remaining strings are a match. If they match, the current substrings will match as well; otherwise, they will not, i.e., dp[i][j] = dp[i – 1][j – 1]. Because we’re presuming our strings start at index 1, we’re using the I – 1)th and (j – 1)th characters to offset empty strings.

Complete Solution

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        rows, columns = (len(s), len(p))
        # Base conditions
        if rows == 0 and columns == 0:
            return True
        if columns == 0:
            return False
        # DP array
        dp = [[False for j in range(columns + 1)] for i in range(rows + 1)]
        # Since empty string and empty pattern are a match
        # print(dp)
        dp[0][0] = True
        # Deals with patterns containing *
        for i in range(2, columns + 1):
            if p[i - 1] == '*':
                dp[0][i] = dp[0][i - 2]
        # For remaining characters
        for i in range(1, rows + 1):
            for j in range(1, columns + 1):
                if s[i - 1] == p[j - 1] or p[j - 1] == '.':
                    dp[i][j] = dp[i - 1][j - 1]
                elif j > 1 and p[j - 1] == '*':
                    dp[i][j] = dp[i][j - 2]
                    if p[j - 2] == '.' or p[j - 2] == s[i - 1]:
                        dp[i][j] = dp[i][j] or dp[i - 1][j]
        return dp[rows][columns]

READ MORE

Python-related posts Visit HERE

C++ related posts Visit HERE

Databases related posts Visit HERE

Data Structures related posts visit HERE

Algorithms related posts visit HERE

Data Science related posts visit HERE