Regular Expression Matching in a Coding Interview: The 2D DP Explained

Regular Expression Matching in a Coding Interview: The 2D DP Explained

Regular Expression Matching in a Coding Interview: The 2D DP Explained

Regular Expression Matching asks whether a string s fully matches a pattern p that uses '.' (any single character) and '*' (zero or more of the preceding element). It looks like a parsing problem, but the clean answer is dynamic programming over two prefixes.

Define the state

Let dp[i][j] be true when s[i:] matches p[j:]. Working from the end means the base case is simple: dp[len(s)][len(p)] is true, because an empty string matches an empty pattern.

The two cases

First check whether the current characters match: first = i < len(s) and p[j] in (s[i], '.'). If the next pattern character is '*', either skip the 'x*' pair entirely (dp[i][j+2]) or, if first matches, consume one character of s and stay on the same pattern position (dp[i+1][j]). Otherwise you need first and dp[i+1][j+1].

def is_match(s, p):
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[m][n] = True
    for i in range(m, -1, -1):
        for j in range(n - 1, -1, -1):
            first = i < m and p[j] in (s[i], '.')
            if j + 1 < n and p[j + 1] == '*':
                dp[i][j] = dp[i][j + 2] or (first and dp[i + 1][j])
            else:
                dp[i][j] = first and dp[i + 1][j + 1]
    return dp[0][0]

What to say out loud

Mention that the star always binds to the previous character, so you look ahead one position instead of behind. Note that i runs to len(s) inclusive, because a pattern like 'a*' can still match an empty remainder. Complexity is O(m*n) time and space, and you can drop to O(n) space with two rows.

Common slip

Candidates often try greedy matching for '*'. Give a counterexample like s='aaa', p='a*a' to show why you must try both options, which is exactly what the DP does.

If you want feedback while you explain recurrences like this, the Linkjob AI interview assistant can help you practise. Disclosure: I help build Linkjob AI.


评论

此博客中的热门博文

Task Scheduler in a Coding Interview: The Idle-Slot Formula Explained

How to Answer "What Motivates You?" in a Job Interview

Cells with Odd Values in a Matrix (LeetCode 1252): Count Rows and Columns, Not Cells