1. Problem Statement (Simple Explanation):
You are given:
A string s (the text).
A pattern p (the regex-like pattern).
You must implement a function:
bool isMatch(string s, string p)
with the following rules:
'.' matches any single character.
'*' matches zero or more of the preceding element (the character just before *).
The entire string s must be matched by the pattern p (no partial match).
This is not full regex; only . and * are supported.
2. Examples:
Example 1:
Input: s = "aa", p = "a"
Output: false
Explanation:
Pattern "a" matches only one 'a'.
String is "aa" (two 'a's).
Entire string is not matched → false.
Example 2:
Input: s = "aa", p = "a*"
Output: true
Explanation:
a* means zero or more 'a'.
It can match "", "a", "aa", "aaa", etc.
So "aa" matches "a*" → true.
Example 3:
Input: s = "ab", p = ".*"
Output: true
Explanation:
. matches any single character.
.* means zero or more of any character.
So ".*" can match any string, including "ab".
Constraints:
1≤∣s∣≤20
1≤∣p∣≤20
s contains only lowercase English letters.
p contains lowercase letters, . and *.
Every * in p has a valid preceding character.
3. Approach 1 – Recursive Backtracking (Conceptual):
This is a natural way to think about it, but can be exponential without memoization.
Key Observations:
p[j] can be:
a normal character ('a'–'z')
a dot ('.')
or a '*', but '*' always applies to the preceding character (p[j-1]).
Consider the state (i, j):
i → current index in s
j → current index in p
We want to know: does s[i:] match p[j:]?
For each position j in pattern:
Case 1: j + 1 < len(p) and p[j+1] == '*'
Then we have two choices for *:Treat * as zero occurrences of p[j]:
Skip p[j] and '*': move to j + 2 (pattern jumps over x*).
Treat * as one or more occurrences, but only if s[i] matches p[j]:
Move i → i + 1 (consume one character from s), stay at j (pattern still at x* to possibly consume more).
Case 2: No * after p[j]
We just match one character:Check if s[i] matches p[j] (same char or '.').
If yes → move to (i+1, j+1), else → fail.
Base Case:
When j == len(p):
Match is successful only if i == len(s) (both strings fully consumed).
This leads to a recursive solution with memoization (DP). But it’s often presented as DP directly.
4. Approach 2 – Dynamic Programming (2D DP, Recommended):
We define a DP table:
dp[i][j] = does s[i:] match p[j:]?
Or equivalently:
dp[i][j] = does the prefix s[0..i-1] match the prefix p[0..j-1]?
We’ll use the prefix version (more common):
i from 0 to len(s)
j from 0 to len(p)
dp[i][j] is true if s[0..i-1] matches p[0..j-1]
Then:
Answer is dp[len(s)][len(p)].
Initialization:
dp[0][0] = true → empty string matches empty pattern.
dp[0][j] (empty string vs pattern):
Pattern like "a*b*c*" can match empty string.
So for j >= 2:
If p[j-1] == '*', then:
dp[0][j] = dp[0][j-2]
(we ignore the preceding char + * pair).
Transition:
For i >= 1, j >= 1:
If p[j-1] is NOT '*' (i.e., normal char or '.'):
We need one character match:
s[i-1] == p[j-1] or p[j-1] == '.'
and the prefixes up to i-1, j-1 must match:
if p[j-1] == s[i-1] or p[j-1] == '.':
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = false
If p[j-1] == '*':
Then it applies to p[j-2] (the preceding element). We have two subcases:
Let x = p[j-2]:
Zero occurrences of x:
Ignore x* pair:
dp[i][j] = dp[i][j-2]
One or more occurrences of x:
Only if x matches s[i-1] (same char or '.'):If s[i-1] matches x, then we can say:
We use one x to match s[i-1], and we keep x* to potentially match more characters.
So:
dp[i][j] = dp[i][j] OR dp[i-1][j]
Combining:
Pseudo-code (DP, Bottom-up):
Complexity:
m=∣s∣
n=∣p∣
Then:
Time: O(m⋅n)
Space: O(m⋅n)
Space can be reduced to O(n) with rolling arrays, but O(mn) is fine given constraints.
5. Java code:
Comments
Post a Comment