Regular Expression Matching

Hard

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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);
}