Regular Expression Matching
Problem
Implement pattern matching where "." matches any single character and "*" matches zero or more of the element just before it. The pattern must match the entire string.
Example 1
Input: s = "aa", p = "a" Output: false
Example 2
Input: s = "aa", p = "a*" Output: true
Example 3
Input: s = "aab", p = "c*a*b" Output: true
Test cases
Case 1
Input: "aa", "a" Expected: false
Case 2
Input: "aa", "a*" Expected: true
Case 3
Input: "ab", ".*" Expected: true
Case 4
Input: "aab", "c*a*b" Expected: true
Case 5
Input: "mississippi", "mis*is*p*." Expected: false
View solutionHide solution1 approach
1. Memoised recursion on (i, j)
Time O(|s|·|p|)Space O(|s|·|p|)
first = s[i] matches p[j] (or "."). If p[j+1] is "*", either skip "x*" (j + 2) or consume one char if first matches (i + 1). Otherwise require first and advance both.
function isMatch(s, p) { const memo = new Map(); const dp = (i, j) => { const key = i * (p.length + 1) + j; if (memo.has(key)) return memo.get(key); let ans; if (j === p.length) ans = i === s.length; else { const first = i < s.length && (p[j] === s[i] || p[j] === '.'); if (p[j + 1] === '*') ans = dp(i, j + 2) || (first && dp(i + 1, j)); else ans = first && dp(i + 1, j + 1); } memo.set(key, ans); return ans; }; return dp(0, 0);}