LeetCode 10: Regular Expression Matching Solution in Python Explained

Problem Statement

LeetCode 10, Regular Expression Matching, is a hard-level challenge where you check if a string s matches a pattern p using basic regular expression rules. The pattern can include letters, dots (.), and stars (*). A dot matches any single character, and a star means the previous character can appear zero or more times. Your task is to return True if the string fully matches the pattern, and False otherwise. It’s like testing if a word fits a special rule set without using Python’s built-in regex tools.

Constraints

  • 0 <= s.length <= 20: String length is 0 to 20 characters.
  • 1 <= p.length <= 20: Pattern length is 1 to 20 characters.
  • s contains lowercase English letters.
  • p contains lowercase letters, ., and *.
  • Every * is preceded by a valid character (letter or dot).

Example

Input: s = "aa", p = "a"
Output: false
Explanation: "a" doesn’t match all of "aa".

Input: s = "aa", p = "a*"
Output: true
Explanation: "a*" means zero or more 'a's, matching "aa".

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

Input: s = "mississippi", p = "mis*is*ip*."
Output: true
Explanation: Pattern matches "mississippi" step by step.

Understanding the Problem

How do you solve LeetCode 10: Regular Expression Matching in Python? It’s about seeing if a string fits a pattern with wildcards. For "aa" and "a", the star lets 'a' repeat, so it matches. For "ab" and ".", the dot-star covers any sequence, so it works. We need to compare s and p character by character, handling * flexibly (zero, one, or many times) and . as a wildcard. We’ll use a Dynamic Programming (DP) approach to break this down systematically.

Solution: Dynamic Programming

Explanation

This solution uses a table to track if parts of the string match parts of the pattern. It’s like building a grid where each cell tells us if a substring matches a subpattern so far.

Here’s a simple visual for "aa" and "a*":

    ""  a  a
""  T   F  F
a   F   T  F
a*  T   T  T
  • Rows are pattern prefixes, columns are string prefixes.
  • T means match, F means no match.
  1. Initialize Table.
  • Create a grid where dp[i][j] is True if the first i pattern characters match the first j string characters.
  1. Set Base Cases.
  • Empty pattern matches empty string (dp[0][0] = True).
  • Pattern with * can match empty string if the * means zero occurrences.
  1. Fill Table.
  • For each pattern and string position, check matches based on letters, dots, or stars.
  1. Return Result.
  • The bottom-right cell (dp[len(p)][len(s)]) shows if the whole string matches.

Step-by-Step Example

Example 1: s = "aa", p = "a*"

We have "aa" and "a*", checking if they match.

  • Goal: See if "aa" fits the pattern "a*".
  • Result for reference: "a*" means zero or more 'a's, so True for "aa".
  • Start: Make a table with 3 rows ("" + "a" + "a*") and 3 columns ("" + "a" + "aa").
  • Step 1: Set up the table.
    • Size is 3x3 (pattern length 2 + 1, string length 2 + 1).
  • Step 2: Base cases.
    • Empty pattern "" vs. empty string "": dp[0][0] = True.
    • Pattern "a" vs. "": dp[1][0] = False (no match).
    • Pattern "a*" vs. "": dp[2][0] = True (star can mean zero 'a's).
  • Step 3: Fill first row (empty pattern).
    • "" vs. "a": dp[0][1] = False.
    • "" vs. "aa": dp[0][2] = False.
  • Step 4: Fill row "a".
    • "a" vs. "a": 'a' matches 'a', dp[1][1] = True.
    • "a" vs. "aa": No match (too short), dp[1][2] = False.
  • Step 5: Fill row "a*".
    • "a*" vs. "a":
      • Zero 'a's: dp[0][1] = False, doesn’t help.
      • One 'a': dp[1][0] = False and 'a' matches 'a', but we check dp[1][1] = True.
      • Result: dp[2][1] = True (star allows one 'a').
    • "a*" vs. "aa":
      • Zero 'a's: dp[0][2] = False.
      • More 'a's: dp[2][1] = True and 'a' matches 'a', so dp[2][2] = True.
  • Finish: dp[2][2] = True.
    • "a*" matches "aa", return True.

Example 2: s = "ab", p = ".*"

Now, "ab" vs. ".*".

  • Goal: Check if "ab" matches ".*".
  • Result for reference: ".*" means any characters, zero or more, so True.
  • Start: Table is 3x3 (pattern ".*" + "", string "ab" + "").
  • Step 1: Base cases.
    • dp[0][0] = True (empty matches empty).
    • dp[1][0] = False ("." vs. "").
    • dp[2][0] = True (".*" vs. "", star means zero).
  • Step 2: Row "".
    • "" vs. "a": dp[0][1] = False.
    • "" vs. "ab": dp[0][2] = False.
  • Step 3: Row ".".
    • "." vs. "a": Dot matches any, dp[1][1] = True.
    • "." vs. "ab": Too short, dp[1][2] = False.
  • Step 4: Row ".*".
    • ".*" vs. "a": Zero: dp[0][1] = False, one: dot matches 'a', dp[2][1] = True.
    • ".*" vs. "ab": Zero: dp[0][2] = False, more: dp[2][1] = True and dot matches 'b', dp[2][2] = True.
  • Finish: dp[2][2] = True.
    • ".*" matches "ab", return True.

Code

Here’s the Python code to solve LeetCode 10. It’s efficient and works in Python 3.6+. Test it on Replit!

def isMatch(s: str, p: str) -> bool:
    m, n = len(s), len(p)
    dp = [[False] * (m + 1) for _ in range(n + 1)]

    # Empty pattern matches empty string
    dp[0][0] = True

    # Handle patterns starting with *
    for i in range(1, n + 1):
        if p[i - 1] == '*':
            dp[i][0] = dp[i - 2][0]

    # Fill the DP table
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if p[i - 1] == '*':
                # Zero occurrences or more
                dp[i][j] = dp[i - 2][j] or (dp[i][j - 1] and (p[i - 2] == s[j - 1] or p[i - 2] == '.'))
            else:
                # Direct match or dot
                dp[i][j] = dp[i - 1][j - 1] and (p[i - 1] == s[j - 1] or p[i - 1] == '.')

    return dp[n][m]

Note: Curious about Python’s list comprehension? Check the official docs.

Complexity

  • Time Complexity: O(m * n) – Fills an m by n table.
  • Space Complexity: O(m * n) – Table size for DP.

Efficiency Notes

This DP solution is optimal for LeetCode 10, balancing speed and clarity. It handles all pattern cases efficiently, making it a top choice for solving regular expression matching in Python.

Key Insights

Tips to master LeetCode 10:

  • **Understand * Flexibility**: It can mean zero, one, or many—check all possibilities.
  • Dot Power: The . matches anything, so it’s a wildcard helper.
  • Build Small First: Start with empty cases and grow the table logically.

These insights can simplify this tricky problem!

Alternative: Recursion (Brief Mention)

Explanation

You could use recursion to match s and p, checking each character and handling * with backtracking. It’s intuitive but slower (exponential time without memoization), so DP is preferred for efficiency.

Additional Example

For s = "aaa", p = "a*a":

  • Goal: Match "aaa" with "a*a".
  • Reference: "a*a" can be 'a' (zero) + 'a', or 'a' + 'aa', so True.
  • Table fills: dp[3][3] = True (details similar to above).
  • Result: True.

Edge Cases

  • Empty String: s = "", p = "a*" – Returns True.
  • No Match: s = "aa", p = "a" – Returns False.
  • All Stars: s = "ab", p = ".*a*" – Returns True.

Final Thoughts

The DP approach is a powerful way to solve LeetCode 10: Regular Expression Matching in Python. It’s great for interviews and teaches pattern matching skills. Want more? Explore LeetCode 5: Longest Palindromic Substring for string fun