DSA problem
Regular Expression Matching
Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:
'.'matches any single character.'*'matches zero or more of the preceding element.
The matching should cover the entire input string (not partial). The crucial difference from wildcard matching is that * here binds to the preceding character (or .), and "zero or more" means we can erase the previous element entirely.
A naive recursion explores many branches; pinning down a polynomial algorithm requires careful state design. Define dp[i][j] as a boolean meaning "s[0..i) matches p[0..j)". The recurrences:
- If
p[j-1] == '*': two cases. Option A — zero occurrences:dp[i][j] = dp[i][j-2](drop thex*pair from the pattern). Option B — one more occurrence: requires the previous pattern character to matchs[i-1](sop[j-2] == s[i-1]orp[j-2] == '.') anddp[i][j] = dp[i][j] || dp[i-1][j]. - If
p[j-1] == '.'orp[j-1] == s[i-1]:dp[i][j] = dp[i-1][j-1]. - Else:
dp[i][j] = false.
Initialize dp[0][0] = true and seed the first row by repeatedly trying to drop x* pairs that match the empty string. Total cost: O(m * n) time and O(m * n) space, easily compressible to two rows.
Examples
s = "aa", p = "a"falses = "aa", p = "a*"trues = "ab", p = ".*"trueConstraints
- 1 <= s.length <= 20
- 1 <= p.length <= 20
- s contains only lowercase English letters.
- p contains only lowercase English letters, '.', and '*'.
- It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.