Regular Expression Match 30 XP Hard

LeetCode Ctrl+Enter Run Ctrl+S Save

Implement regex matching supporting '.' (any single char) and '*' (zero or more of preceding element). Must match the entire string.

# s='aab', p='c*a*b' → True
# c* matches 0 c's, a* matches 2 a's, b matches b

2D DP: dp[i][j] = True if s[:i] matches p[:j]. Handle '*' by either using 0 occurrences (dp[i][j-2]) or matching one more (dp[i-1][j] if chars match).

💡 Pro tip: Understand this problem deeply — don't just memorize the code. Try explaining the approach out loud as if teaching a friend. If you can explain it simply, you truly understand it!

📋 Instructions

Test regex matching: 'aa' matches 'a*' → True 'ab' matches '.*' → True 'aab' matches 'c*a*b' → True

dp[0][0]=True. Handle p[j-1]=='*': dp[i][j] = dp[i][j-2] (0 match) or dp[i-1][j] if chars match (1+ match).

🧪 Test Cases

Input

isMatch('aa', 'a*')

Expected

True

Boolean check

Input

isMatch('ab', '.*')

Expected

True

Boolean check

Input

isMatch('aab', 'c*a*b')

Expected

True

Boolean check

← Previous 🎉 Finish Course

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›