Regular Expression Matching — Java Coding Problem
Difficulty: hard | Category: dynamic-programming
Problem Description
Given an input string `s` and a pattern `p`, implement regular expression matching with support for `'.'` and `'*'`. - `'.'` matches any single character. - `'*'` matches zero or more of the preceding element. The matching must cover the **entire** input string. Hint: 2D DP. `dp[i][j]` = true if `s[0..i]` matches `p[0..j]`. Handle the `'*'` case by checking zero occurrences (`dp[i][j-2]`) or one-or-more (`dp[i-1][j]` when the preceding pattern character matches `s[i-1]`).
Examples
Example 1
Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2
Input: s = "aa", p = "a*"
Output: true
Explanation: "a*" matches any number of "a"s.
Example 3
Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" matches any string.
Example 4
Input: s = "aab", p = "c*a*b"
Output: true
Explanation: "c*" matches 0 "c"s, "a*" matches 2 "a"s, then "b".