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.
评论
发表评论