LeetCode 10 Solution: Regular Expression Matching

If you’re looking to crack hard LeetCode problems, the “LeetCode 10 solution” is a fantastic start. It will help improve your understanding of dynamic programming and string manipulation. This problem involves implementing a regular expression matching algorithm, where you’re given two strings: the input text and a pattern. The key difficulty here lies in the fact that the pattern can include two special characters:

• The dot (.) matches any single character.
• The asterisk (*) matches zero or more occurrences of the preceding character.

Let’s break down the solution to this problem using dynamic programming.

Understanding the Regular Expression Matching Problem

The problem might seem tricky at first glance because of the way the . and * operators work. The . operator makes matching slightly more flexible by matching any single character, while the * adds complexity by allowing zero or more repetitions of the character preceding it.

For example, the input string "aa" with the pattern "a" doesn’t match because the pattern only expects one a. However, if the pattern is "a*", it can match zero or more occurrences of a, which will match "aa". Similarly, the pattern ".*" is extremely flexible since it can match any number of any characters, meaning it can match any string.

To solve this problem efficiently, we can use dynamic programming, where the idea is to break the problem down into smaller subproblems and store intermediate results to avoid redundant computations.

Dynamic Programming Approach for LeetCode 10 Solution

In the LeetCode 10 solution, we use a two-dimensional table to represent whether substrings of the input text match substrings of the pattern. We construct a dp table where dp[i][j] tells us whether the substring text[i:] matches the substring pattern[j:]. This approach allows us to handle complex cases where * and . are involved.

The base case of this dynamic programming solution is straightforward: an empty string matches an empty pattern, so dp[-1][-1] is set to True. This forms the foundation for building the rest of the table.

To fill the table, we iterate over the string and the pattern from the end to the beginning. For each character in the pattern, we check whether it matches the current character in the input string. If there’s a match (or if the pattern contains .), we rely on previously computed values in the dp table to determine if the match is valid.

Handling the * operator requires a bit more care. The * can match zero occurrences of the preceding character, or it can match one or more occurrences. In this case, we update our dp table by either ignoring the * and its preceding character or checking if repeating the preceding character helps in forming a match.

This method ensures that the entire input string matches the pattern if and only if dp[0][0] is True at the end of the algorithm.

Code Implementation of the LeetCode 10 Solution

We structure our python code for the LeetCode 10 solution around dynamic programming principles. Here’s a working implementation:

def isMatch(self, text: str, pattern: str) -> bool:
    # Step 1
    dp = [[False] * (len(pattern) + 1) for _ in range(len(text) + 1)]
    dp[-1][-1] = True

    # Step 2
    for i in range(len(text), -1, -1):
        for j in range(len(pattern) - 1, -1, -1):
            first_match = i < len(text) and pattern[j] in {text[i], "."}
            if j + 1 < len(pattern) and pattern[j + 1] == "*":
                dp[i][j] = dp[i][j + 2] or first_match and dp[i + 1][j]
            else:
                dp[i][j] = first_match and dp[i + 1][j + 1]

    return dp[0][0]

Step-by-Step Explanation of the LeetCode 10 Solution

Let’s walk through the algorithm step-by-step with a non-trivial case to see how the dynamic programming table is filled and how the pattern matching unfolds. We’ll use the following example:

• Input text: "aab"
• Pattern: "c*a*b"

Here, the pattern contains both * and regular characters, so it’s a good case to explore the algorithm’s behavior.

Step 1: Initialize the DP Table

First, we create a DP table of size (len(text) + 1) x (len(pattern) + 1) to handle all possible substrings of text and pattern. The DP table is initialized to False, except dp[-1][-1], which is True because an empty pattern matches an empty text.

i \ j	0. ‘c‘	1. ‘*‘	2. ‘a‘	3. ‘*‘	4. ‘b‘	5.
0. ‘a‘	False	False	False	False	False	False
1. ‘a‘	False	False	False	False	False	False
2. ‘b‘	False	False	False	False	False	False
3.	False	False	False	False	False	True

Notes:

• i ranges from 0 to 3, representing positions in input, with input[i] shown.
• j ranges from 0 to 5, representing positions in pattern, with pattern[j] shown.
• The bottom-right cell dp[3][5] is set to True.
• Each cell represents whether text[i:] matches pattern[j:].

Step 2: Populate the DP Table

Now, we start filling the DP table from the bottom-right corner, working backwards to match substrings of text and pattern. See the two for loops.

Iteration 1

• i = 3 – empty string in input
• j = 4 – character 'b'in pattern
• first_match = False
• The condition is False, and we proceed to the else clause.
• Because of first_match = False, we update d[i][j] = False

Explanation

• At i = 3, j = 4, we’re comparing an empty input (input[3:] = "") with the pattern starting at 'b' (pattern[4:] = "b").
• Since input is empty and pattern is not, first_match is False.
• There’s no '*' to account for zero occurrences, so dp[3][4] remains False.

Conclustion: an empty text does not match the pattern 'b'.

i \ j	0. ‘c‘	1. ‘*‘	2. ‘a‘	3. ‘*‘	4. ‘b‘	5.
0. ‘a‘	False	False	False	False	False	False
1. ‘a‘	False	False	False	False	False	False
2. ‘b‘	False	False	False	False	False	False
3.	False	False	False	False	False	True

Final DB table

i \ j	0. ‘c‘	1. ‘*‘	2. ‘a‘	3. ‘*‘	4. ‘b‘	5.
0. ‘a‘	True	False	True	False	False	False
1. ‘a‘	True	False	True	False	False	False
2. ‘b‘	True	False	True	False	True	False
3.	False	False	False	False	False	True

• True: The substring input[i:] matches the subpattern pattern[j:].
• False: The substring input[i:] does not match the subpattern pattern[j:].

Explanation of the DP Table

• Base Case (dp[3][5] = True):
  • An empty text matches an empty pattern.
• dp[0][0] = True:
  • The entire input matches the entire pattern.
  • This is the value we’re interested in for the final result.
• Understanding Key Cells:
  • dp[2][4] = True:
    • The substring "b" matches the pattern "b".
  • dp[1][2] = True:
    • The substring "ab" matches the pattern "a*b".
  • dp[0][0] = True:
    • The entire text "aab" matches the entire pattern "c*a*b".

Analysis of the Solution for LeetCode 10

This dynamic programming solution performs efficiently within the problem constraints. Given that both the text and the pattern can have a length of up to 20 characters, the algorithm’s time complexity of O(m * n) is suitable. Here, m is the length of the input and n is the length of the pattern. The space complexity is also O(m * n) because of the 2D table used to store intermediate results.

This algorithm is particularly effective because it handles both simple cases and complex patterns involving multiple asterisks and dots. Fill the DP table from the end of the string and pattern to the beginning to ensure that you consider every possible substring combination. The two main operations—handling a regular character or . and managing the * operator—are done in constant time for each element in the table.

Edge Cases and Examples

To better understand how this solution works, consider a few edge cases. If the text is empty and the pattern is "a*", the solution correctly identifies that the pattern can match zero occurrences of a, and thus returns True. Similarly, if the pattern contains only dots and asterisks, like "aab" and ".*", the solution efficiently matches the entire string since .* can represent any number of any characters.

On the other hand, mismatches like "aa" and "a" are handled by the algorithm, returning False because the single a in the pattern doesn’t cover the entire string "aa".

Conclusion

The LeetCode 10 solution is an excellent demonstration of dynamic programming in action. It efficiently solves the problem by breaking the task into smaller subproblems. Leveraging previous computations to form a complete solution. Whether you’re new to dynamic programming or looking to improve your skills with string manipulation problems, this solution provides a clear and robust approach.

Understand the key concepts behind the dot and asterisk operators, and see how they influence the matching process. This knowledge will equip you to tackle similar problems on LeetCode. If you’re preparing for coding interviews, mastering the LeetCode 10 solution is a great way to strengthen your problem-solving toolkit.

Happy Coding!

---

Looking for more LeetCode solutions? Stay tuned for upcoming guides on tackling other LeetCode challenges in Python. Whether you’re preparing for technical interviews or aiming to improve your coding skills, exploring a variety of problems will enhance your understanding and proficiency.

You can find this problem on LeedCode, click here.