Regular Expression Matching Leetcode Problem 10 [Python Solution]

Here we face the challenge Regular Expression Matching LeetCode problem where we’ll explore a Python solution to efficiently solve this problem.

Regular Expression Matching is a hard problem in the category of 2-D Dynamic Programming, and it’s associated with companies like Google.

If you’re looking for a solution to this problem, you’ve come to the right place!

Problem Overview

LeetCode Problem Link: Regular Expression Matching

Regular Expression Matching involves matching an input string s with a given pattern p.

The pattern can contain two special characters:

• .: This matches any single character.
• *: This matches zero or more of the preceding element.

The goal is to determine if the pattern covers the entire input string, not just a partial match.

Example 1:

Let’s begin with an example.

Suppose we have an input string s = "aa" and a pattern p = "a".

In this case, the output should be false because the pattern “a” does not match the entire string “aa.”

Example 2:

Now, let’s consider a different scenario.

If our input string is s = "aa" and the pattern is p = "a*", the output should be true.

This is because the asterisk * allows zero or more repetitions of the preceding element.

In this case, repeating ‘a’ once results in “aa.”

Example 3:

Another example: if s = "ab" and p = ".*", the output should again be true.

The “.” pattern means “zero or more () of any character (.)”.

In this case, it matches any character and allows the pattern to match the input string “ab.”

Constraints:

Before we dive into the solutions, let’s understand the constraints:

• The length of the input string s is between 1 and 20.
• The length of the pattern p is between 1 and 20.
• The input string s consists only of lowercase English letters.
• The pattern p consists of lowercase English letters, ‘.’, and ‘*’.

It is guaranteed that for each appearance of the character ‘*’, there will be a previous valid character to match.

Understanding Regular Expression Constraints

To solve this problem efficiently, we need to understand the constraints and the dynamics of regular expressions.

Regular expressions are a powerful way to define patterns in text.

In this context, we need to consider the following:

• The period . matches any character.
• The asterisk * allows for zero or more repetitions of the preceding element.

These constraints make the problem quite intricate, but with a well-thought-out approach, we can solve it.

Regular Expression Matching LeetCode Problem Solution

Now, let’s delve into solving the Regular Expression Matching problem efficiently.

We’ll explore two approaches: the bottom-up dynamic programming solution and the top-down memoization solution.

1. Bottom-Up Dynamic Programming

def isMatchBottomUp(s: str, p: str) -> bool:
    cache = [[False] * (len(p) + 1) for i in range(len(s) + 1)]
    cache[len(s)][len(p)] = True

    for i in range(len(s), -1, -1):
        for j in range(len(p) - 1, -1, -1):
            match = i < len(s) and (s[i] == p[j] or p[j] == ".")

            if (j + 1) < len(p) and p[j + 1] == "*":
                cache[i][j] = cache[i][j + 2]
                if match:
                    cache[i][j] = cache[i + 1][j] or cache[i][j]
            elif match:
                cache[i][j] = cache[i + 1][j + 1]

    return cache[0][0]

2. Top-Down Memoization

def isMatch(self, s: str, p: str) -> bool:
        cache = {}

        def dfs(i, j):
            if (i, j) in cache:
                return cache[(i, j)]
            if i >= len(s) and j >= len(p):
                return True
            if j >= len(p):
                return False

            match = i < len(s) and (s[i] == p[j] or p[j] == ".")
            if (j + 1) < len(p) and p[j + 1] == "*":
                cache[(i, j)] = dfs(i, j + 2) or (match and dfs(i + 1, j))
                return cache[(i, j)]
            if match:
                cache[(i, j)] = dfs(i + 1, j + 1)
                return cache[(i, j)]
            cache[(i, j)] = False
            return False

        return dfs(0, 0)

Related Interview Questions By Company:

• Find Median From Data Stream LeetCode
• First Missing Positive LeetCode
• Find Critical And Pseudo Critical Edges In Minimum Spanning Tree

Related Interview Questions By Difficulty:

• Count Vowels Permutation LeetCode
• Unique Paths II LeetCode
• Last Stone Weight II LeetCode

Related Interview Questions By Category:

• Minimum Path Sum LeetCode
• Interleaving String LeetCode
• Remove Duplicates From Sorted List LeetCode

Conclusion

The Regular Expression Matching problem is a challenging LeetCode problem, but with the right approach, you can efficiently solve it.

We explored two solutions: the bottom-up dynamic programming approach and the top-down memoization approach.

These solutions provide a clear understanding of how to match regular expressions efficiently.

Regular expressions are a powerful tool for text pattern matching, and mastering them can be invaluable for various programming tasks.

Happy coding!