Mahdi Shamlou | Solving LeetCode #10: Regular Expression Matching — Step by Step

Hey everyone! Mahdi Shamlou here — back with another LeetCode problem!

After solving LeetCode #9 — Palindrome Number, today I want to share my experience solving Problem #10 — Regular Expression Matching.

This problem was a little different from the previous ones. At first, I thought about checking characters one by one, but after understanding the behavior of . and *, I realized that I needed a different approach.

Let's see how I approached it.

Problem Statement

Given an input string s and a pattern p, implement regular expression matching with support for:

• . Matches any single character.
• * Matches zero or more of the preceding element.

The matching should cover the entire input string, not just a part of it.

Examples

Example 1:

Input: s = "aa", p = "a"
Output: False

The pattern does not match the entire string.

Example 2:

Input: s = "aa", p = "a*"
Output: True

Because * means zero or more occurrences of the preceding character, a* can match aa.

Example 3:

Input: s = "ab", p = ".*"
Output: True

Here, . matches any character and * allows it to repeat.

Understanding the Problem

Before writing any code, I needed to understand two important rules.

1. The Dot (.)

The dot matches any single character.

For example:

a.c

This pattern can match:

abc
a1c
a-c

2. The Star (*)

The star matches zero or more occurrences of the element immediately before it.

For example:

a*

Can match:

""
"a"
"aa"
"aaa"
"aaaa"

This is where the problem becomes more interesting.

We cannot simply compare characters from left to right because * can change how many characters we need to match.

My Thought Process

When I started solving this problem, I realized that simple character-by-character comparison would not be enough.

I needed to consider previous matching results because the current character could depend on what happened before it.

That's when I decided to use Dynamic Programming (DP).

My idea was to create a two-dimensional matrix to store the matching results.

Instead of calculating the same matching conditions repeatedly, I could save the results and use them in the next steps.

My Solution

I created a matrix with the following dimensions:

(m + 1) x (n + 1)

Where:

• m is the length of the input string.
• n is the length of the pattern.

Each cell represents whether a prefix of the input string matches a prefix of the pattern.

Here is my implementation:

class Solution:
    def isMatch(self, s: str, p: str) -> bool:

        m, n = len(s), len(p)

        # Create the DP matrix
        my_matrix = [[False] * (n + 1) for _ in range(m + 1)]

        # Base case: empty string matches empty pattern
        my_matrix[0][0] = True

        # Handle patterns that can match an empty string
        for j in range(2, n + 1):
            if p[j - 1] == '*':
                my_matrix[0][j] = my_matrix[0][j - 2]

        # Fill the DP matrix
        for i in range(1, m + 1):
            for j in range(1, n + 1):

                if p[j - 1] == s[i - 1] or p[j - 1] == '.':
                    my_matrix[i][j] = my_matrix[i - 1][j - 1]

                elif p[j - 1] == '*':
                    my_matrix[i][j] = (
                        my_matrix[i][j - 2]
                        or (
                            my_matrix[i - 1][j]
                            and (
                                s[i - 1] == p[j - 2]
                                or p[j - 2] == '.'
                            )
                        )
                    )

        return my_matrix[m][n]

How It Works

Let's understand the most important parts of the implementation.

1. Creating the Matrix

my_matrix = [[False] * (n + 1) for _ in range(m + 1)]

I created a matrix to store the matching results.

For example, if:

s = "aa"
p = "a*"

The matrix has 3 rows and 3 columns.

Why?

Because we also need to consider empty prefixes.

2. Initializing the Matrix

my_matrix[0][0] = True

An empty string matches an empty pattern.

But what happens when the pattern contains *?

For example:

s = ""
p = "a*"

This should return True because a* can match zero occurrences of a.

That's why I added this initialization:

for j in range(2, n + 1):
    if p[j - 1] == '*':
        my_matrix[0][j] = my_matrix[0][j - 2]

This allows patterns containing * to match an empty string when appropriate.

3. Handling Normal Characters and Dot

if p[j - 1] == s[i - 1] or p[j - 1] == '.':
    my_matrix[i][j] = my_matrix[i - 1][j - 1]

If the current characters match, or the pattern contains ., we use the result from the previous row and previous column.

In other words, both current characters match, so we continue checking the remaining prefixes.

4. Handling Star (*)

This is the most important part:

elif p[j - 1] == '*':
    my_matrix[i][j] = (
        my_matrix[i][j - 2]
        or (
            my_matrix[i - 1][j]
            and (
                s[i - 1] == p[j - 2]
                or p[j - 2] == '.'
            )
        )
    )

There are two possible situations.

Case 1: Star matches zero occurrences

my_matrix[i][j - 2]

We ignore the preceding character and * together.

For example:

Pattern: a*

If * matches zero occurrences, we can treat a* as an empty pattern.

Case 2: Star matches one or more occurrences

my_matrix[i - 1][j]

If the current input character matches the character before *, we can keep using the same pattern and check the previous input character.

The preceding character can also be . because it matches any character.

Combining these two cases gives us the complete condition for handling *.

Complexity Analysis

Let's analyze the performance of this solution.

Time Complexity

O(m * n)

Where:

• m is the length of the input string.
• n is the length of the pattern.

We have two nested loops, and each iteration performs a constant amount of work.

Therefore, the time complexity is O(m * n).

Space Complexity

O(m * n)

We create a two-dimensional matrix with (m + 1) * (n + 1) elements.

So the space complexity is also O(m * n).

Final Thoughts

Regular Expression Matching was definitely more challenging than some of the previous LeetCode problems I solved.

The interesting part was not writing the nested loops. It was understanding how to define the DP states and how each state depends on previous states.

This is one of the things I enjoy about solving LeetCode problems: sometimes the biggest challenge is finding the right way to think about a problem.

What About You?

How did you solve this problem?

I'd love to hear about your solution and how you approached this problem!

My Repository

GitHub — mahdi0shamlou/LeetCode

More LeetCode solutions coming soon!

Author: Mahdi Shamlou
نویسنده: مهدی شاملو