Regular Expression Matching
The drill: Match a string against a pattern where '.' stands in for any single character and '*' means zero or more of the character right before it — the match has to cover the whole string, not just a piece of it.
A text string and a pattern arrive together. The pattern's characters are ordinary except for two: '.' matches any single character, and '*' means zero or more repetitions of whatever character sits directly before it in the pattern.
A match has to account for the text's entire length, start to finish — a pattern that only matches a prefix or a middle slice of the text doesn't count. Trailing stars that absorb zero characters still count as full participants in that check.
The drill is a yes/no verdict: does the given pattern, applied under these two rules, match the whole text exactly.
- text and pattern hold lowercase letters plus the special tokens '.' and '*'
- a '*' always follows some character or '.' — it never appears on its own
- the match must span the entire text, not a substring of it
- lengths of both text and pattern stay small enough for quadratic-ish work
HINT 1 THE NUDGE
A trailing '*' is the only place the pattern can 'give up' characters without consuming the string — everywhere else, one pattern token consumes exactly one string character, or the whole match fails. Where does that leave a pattern with no stars in it?
HINT 2 THE STRUCTURE
Read the pattern two tokens at a time. If the next token is followed by '*', there's a real choice: skip that token-and-star pair entirely (zero occurrences), or, if the current string character fits the token, consume one character and stay on the same star (one more occurrence).
HINT 3 ONE STEP FROM THE ANSWER
dp(i, j): when pattern[j] is followed by '*', dp(i,j) = dp(i, j+2) OR (charMatches AND dp(i+1, j)). Otherwise dp(i,j) = charMatches AND dp(i+1, j+1). Running out of string with pattern left over only survives if every remaining token is a zero-occurrence star.
s='aab', p='c*a*b'. dp[i][end] is true only when the string is fully consumed too — true only at i=3, past the last letter.
class Solution:
def isMatch(self, s: str, p: str) -> bool:
n, m = len(s), len(p)
@functools.lru_cache(maxsize=None)
def rec(i, j):
if j == m:
return i == n
first = i < n and (p[j] == s[i] or p[j] == '.')
if j + 1 < m and p[j + 1] == '*':
return rec(i, j + 2) or (first and rec(i + 1, j))
return first and rec(i + 1, j + 1)
return rec(0, 0)class Solution:
def isMatch(self, s: str, p: str) -> bool:
n, m = len(s), len(p)
def rec(i, j):
if j == m:
return i == n
first = i < n and (p[j] == s[i] or p[j] == '.')
if j + 1 < m and p[j + 1] == '*':
return rec(i, j + 2) or (first and rec(i + 1, j))
return first and rec(i + 1, j + 1)
return rec(0, 0)class Solution {
private String s, p;
private int n, m;
private Boolean[][] memo;
public boolean isMatch(String s, String p) {
this.s = s;
this.p = p;
n = s.length();
m = p.length();
memo = new Boolean[n + 1][m + 1];
return rec(0, 0);
}
private boolean rec(int i, int j) {
if (j == m) return i == n;
if (memo[i][j] != null) return memo[i][j];
boolean first = i < n && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.');
boolean result;
if (j + 1 < m && p.charAt(j + 1) == '*') {
result = rec(i, j + 2) || (first && rec(i + 1, j));
} else {
result = first && rec(i + 1, j + 1);
}
memo[i][j] = result;
return result;
}
}class Solution {
private String s, p;
private int n, m;
public boolean isMatch(String s, String p) {
this.s = s;
this.p = p;
n = s.length();
m = p.length();
return rec(0, 0);
}
private boolean rec(int i, int j) {
if (j == m) return i == n;
boolean first = i < n && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.');
if (j + 1 < m && p.charAt(j + 1) == '*') {
return rec(i, j + 2) || (first && rec(i + 1, j));
}
return first && rec(i + 1, j + 1);
}
}✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED