Wildcard matching
AmazonThe problem
Given a string str and a pattern pat, implement a pattern matching function that supports the following special characters:
'?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence).
The pattern must match the entire string.
Input: str = "xaylmz", pat = "x?yz" Output: true **Explanation: ** The pattern "x?yz" matches the string "xaylmz":
- '?' matches 'a'
- '*' matches "lm"
- 'z' matches 'z'
Input: str = "xyza", pat = "xz" Output: false **Explanation: ** The pattern "xz" does not match the string "xyza" because there is an extra 'a' at the end of the string that is not matched by the pattern.
**Input: **str = "abc", par = "a?c"
- 0 <= length of(str, pattern) <= 200
cpp
class Solution {
public:
bool wildCard(string str, string pat) {
}
};java
class Solution {
public boolean wildCard(String str, String pat) {
}
}python
class Solution:
def wildCard(self, str: str, pat: str) -> bool:javascript
class Solution {
wildCard(str, pat) {
}
}csharp
class Solution
{
public bool WildCard(string str, string pat)
{
}
}go
func wildCard(str, pat string) bool {
}Stuck? Show a way to structure it+
- 01Define dp[i][j] for whether prefixes of s and pattern match.
- 02Match equal characters or `?` from the diagonal state.
- 03For `*`, combine matching empty (`dp[i][j-1]`) or one more character (`dp[i-1][j]`).
- 04Initialize the empty-string row so only all-star prefixes match.
Reference answer
Then expect these follow-ups
How would you reduce the DP to O(m) space?
Tests: space optimization
When is the greedy two-pointer solution valid?
Tests: algorithm trade-offs
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question