Regular Expression Matching (LeetCode 10)

The problem

Implement matching for a pattern p against a string s, where:

• '.' matches any single character, and
• '*' means zero or more copies of the character just before it.

The match must cover the whole string. s contains lowercase letters; p contains lowercase letters, '.' and '*', and every '*' follows a valid character.

Input:  s = "aab", p = "c*a*b"
Output: True

c* matches zero cs, a* matches "aa", and b matches b.

How to think about it

Start with brute force. Recursively match character by character, and at each x* try “use it zero times” and “use it once more”. Without memoisation the branching blows up on patterns like a*a*a*a*b, giving exponential time.

The key insight: the state is two prefix lengths. Let dp[i][j] mean ”s[:i] matches p[:j]”. Look at the last pattern character p[j-1]:

• A letter or '.': it must match s[i-1], and the rest must match: dp[i][j] = dp[i-1][j-1].
• A '*': the pair x* (where x = p[j-2]) has two options. Zero copies: drop the pair, dp[i][j-2]. One more copy: if x matches s[i-1], consume that character and stay on the same pattern position, dp[i-1][j]. Either option is enough.

The empty-string row is not all False. Patterns like a* or a*b* match the empty string. So dp[0][j] = dp[0][j-2] whenever p[j-1] is '*'.

Which pattern is this? 2-D DP over two sequences (string vs pattern). The tell is “does this pattern match the whole string” with a repetition operator; the star’s “stay on j” step is what makes it unbounded.

Approach

1. Make a (len(s) + 1) × (len(p) + 1) table of False, with dp[0][0] = True.
2. Fill row 0: for each '*' at p[j-1], set dp[0][j] = dp[0][j-2].
3. For each i ≥ 1, j ≥ 1:
   • If p[j-1] is '*': start with dp[i][j-2] (zero copies). If p[j-2] is '.' or equals s[i-1], also allow dp[i-1][j].
   • Else if p[j-1] is '.' or equals s[i-1]: dp[i][j] = dp[i-1][j-1].
4. Return dp[-1][-1].

Solution

def is_match(s, p):
    dp = [[False]*(len(p)+1) for _ in range(len(s)+1)]   # dp[i][j]: s[:i] matches p[:j]
    dp[0][0] = True
    for j in range(1, len(p)+1):
        if p[j-1] == '*': dp[0][j] = dp[0][j-2]   # x* can match the empty string
    for i in range(1, len(s)+1):
        for j in range(1, len(p)+1):
            if p[j-1] == '*':
                dp[i][j] = dp[i][j-2]             # zero copies of x
                if p[j-2] == '.' or p[j-2] == s[i-1]: dp[i][j] = dp[i][j] or dp[i-1][j]   # one more x
            elif p[j-1] == '.' or p[j-1] == s[i-1]:
                dp[i][j] = dp[i-1][j-1]           # single-character match
    return dp[-1][-1]
# is_match("aa", "a*") -> True ;  is_match("mississippi", "mis*is*p*.") -> False

Dry run

The table for s = "aab" (rows) and p = "c*a*b" (columns), 1 = True:

Row 0: c* and c*a* both match the empty string. In row 2, the * column is 1 because a matches and the cell above ("a" vs c*a*) is 1: “one more a”. The bottom-right cell is 1, so the answer is True.

Complexity

• Time: O(m · n). Each cell is constant work.
• Space: O(m · n) for the table; two rows suffice if you roll it.

Edge cases and pitfalls

• Empty string with a star pattern: is_match("", "a*b*") is True; forgetting the row-0 setup gets this wrong.
• ".*" matches everything, including the empty string.
• The star applies to the previous character, not to everything before it. "ab*" means a followed by any number of bs.
• Partial matches don’t count. is_match("aa", "a") is False.

Related problems

• Edit Distance (LeetCode 72): the same prefix-pair table, with costs instead of booleans.
• Interleaving String (LeetCode 97): a boolean two-string DP with similar transitions.
• Word Break (LeetCode 139): a simpler boolean “can this string be matched” DP over prefixes.