1. Problem Statement (Simple Explanation):
You’re given:
A string s (text).
A pattern p that may contain:
lowercase letters
'?' which matches any single character
'*' which matches any sequence of characters (including empty)
You must determine if the entire string s matches the entire pattern p (no partial match).
2. Examples:
Example 1:
Input: s = "aa", p = "a"
Pattern "a" is only one character; s has two characters → cannot match entire string.
Output: false
Example 2:
Input: s = "aa", p = "*"
'*' can match any sequence, including "aa".
Output: true
Example 3:
Input: s = "cb", p = "?a"
'?' matches 'c'
'a' must match 'b' → mismatch
Output: false
Constraints:
0 <= s.length, p.length <= 2000
s has only lowercase letters.
p has lowercase letters, '?', '*'.
3. Approaches Overview:
Common approaches:
Greedy with backtracking on * positions – O(m+n) average, O(1) extra space; standard and efficient.
Dynamic Programming (2D DP) – O(m·n) time, O(m·n) space (or O(n) space optimized).
For interviews & large constraints, the greedy two-pointer with * backtracking is usually preferred.
I’ll focus on that, and briefly mention DP.
4. Greedy Two-Pointer Algorithm with * Backtracking:
Intuition:
We scan the string s and pattern p from left to right:
Maintain:
i – index in s
j – index in p
starIdx – last position of '*' in p (-1 if none)
matchIdx – position in s corresponding to the match right after the last '*'
Rules:
If p[j] is a letter or '?' and matches s[i]:
Move both pointers: i++, j++.
If p[j] is '*':
Record its position: starIdx = j.
Record matchIdx = i (position in s where * starts matching).
Move j++ (treat * as matching empty for now).
If there is a mismatch:
If we previously saw a '*' (starIdx != -1):
Backtrack: interpret the last '*' as matching one more character in s:
j = starIdx + 1
matchIdx++
i = matchIdx
Else:
No '*' to adjust → match fails → return false.
After traversing s (i.e., i == len(s)):
There may still be remaining characters in p.
They must all be '*' to match empty; skip trailing '*'.
If j reaches len(p), match is successful; otherwise, fail.
This approach allows '*' to be flexibly expanded or shrunk as needed.
Pseudo-code (Greedy):
Let m = len(s), n = len(p):
Time: O(m + n) worst/typical case.
Space: O(1) extra.
5. DP Approach (High-level)(Optimal):
Define dp[i][j]:
true if s[0..i-1] matches p[0..j-1].
Transition:
If p[j-1] is a letter or '?':
dp[i][j] = dp[i-1][j-1] && (p[j-1] == s[i-1] or p[j-1] == '?')
If p[j-1] == '*':
dp[i][j] = dp[i][j-1] /* * as empty */ OR dp[i-1][j] /* * matches one more char */
Base cases:
dp[0][0] = true
dp[0][j] = dp[0][j-1] if p[0..j-1] are all '*'.
This yields an O(m·n) time solution.
6. Java code:
8. C++ code:
9. Python code:
10. JavaScript code:
Comments
Post a Comment