← Benches
ladder.coding.wildcard_match
CodinggauntletAn owned ladder bench, graded mechanically against a fixed test.
Solved
28/35
runs passed
Models
22
have attempted
Harnesses
5
scaffolds tried
Runs (latest per model × harness — solved sorted first)
| Model | Harness | Result | Turns | tok/s | Latency | Ctx | When |
|---|---|---|---|---|---|---|---|
| gemma-4-26b-a4b-it | bare | PASS | — | — | 13.0s | 64k | 2026-06-23 |
| gemma-4-26b-a4b-it | dev_cycle | PASS | — | — | 12.9s | 64k | 2026-06-23 |
| gemma-4-26b-a4b-it | structured_feedback | PASS | 1 | — | — | 64k | 2026-06-23 |
| gpt-oss-120b | baseline | PASS | 1 | 52.6 | 7.4s | 64k | 2026-06-23 |
| gpt-oss-20b | bare | PASS | 1 | — | — | 64k | 2026-06-23 |
| gpt-oss-20b | dev_cycle | PASS | 1 | — | — | 64k | 2026-06-23 |
| gpt-oss-20b | structured_feedback | PASS | 1 | — | — | 64k | 2026-06-23 |
| llama-3.3-70b | baseline | PASS | 1 | 2.8 | 2.1m | 64k | 2026-06-23 |
| qwen3.6-35b-a3b | bare | PASS | — | — | 1.8m | 64k | 2026-06-23 |
| qwen3.6-35b-a3b | dev_cycle | PASS | — | — | 1.9m | 64k | 2026-06-23 |
| qwen3.6-35b-a3b | structured_feedback | PASS | 1 | — | — | 64k | 2026-06-23 |
| devstral-small-2-2512 | baseline | PASS | 1 | 8.5 | 28.8s | 128k | 2026-06-23 |
| mistral-small-3.1-24b-instruct-2503 | baseline | PASS | 1 | 8.6 | 28.3s | 128k | 2026-06-23 |
| qwen3.5-122b-a10b-cluster | baseline | PASS | 1 | 16.3 | 4.7m | 64k | 2026-06-29 |
| gpt-oss-20b | baseline | PASS | 1 | 79.0 | 8.4s | 64k | 2026-07-01 |
| qwen3-coder-30b | baseline | PASS | 1 | 36.3 | 9.0s | 64k | 2026-07-01 |
| gemma-4-26b-a4b-it | baseline | PASS | 1 | 28.7 | 20.7s | 64k | 2026-07-01 |
| qwen3.6-35b-a3b-or | baseline | PASS | 1 | 125.3 | 58.2s | 64k | 2026-07-01 |
| gemini-2.5-flash-lite | baseline | PASS | 1 | 240.5 | 1.8s | 64k | 2026-07-01 |
| qwen3.6-35b-bf16 | baseline | PASS | 1 | 34.3 | 3.3m | 64k | 2026-07-02 |
| granite-4.1-30b | baseline | PASS | 1 | 7.4 | 28.9s | 64k | 2026-07-02 |
| qwen3.6-27b | v1.7.1 | PASS | 1 | 8.1 | 48.0s | 64k | 2026-07-02 |
| qwen3-next-80b | baseline | PASS | 1 | 45.7 | 6.5s | 64k | 2026-07-02 |
| phi-4-reasoning-plus | baseline | PASS | 1 | 14.0 | 7.0m | 64k | 2026-07-02 |
| deepseek-r1-distill-qwen-32b | baseline | PASS | 1 | 6.5 | 2.0m | 64k | 2026-07-03 |
| qwen3.6-35b-a3b | baseline | PASS | 1 | 55.1 | 6.8s | 64k | 2026-07-05 |
| qwen3.6-27b | baseline | PASS | 1 | 7.7 | 50.0s | 64k | 2026-07-05 |
| claude-sonnet-4.6 | baseline | PASS | 1 | 54.3 | 6.1s | 195k | 2026-07-06 |
| granite-4.1-8b | baseline | fail | 1 | 22.7 | 6.0s | 64k | 2026-06-23 |
| qwen3.5-4b | bare | fail | 1 | — | — | 64k | 2026-06-23 |
| qwen3.5-4b | dev_cycle | fail | 3 | — | — | 64k | 2026-06-23 |
| qwen3.5-4b | structured_feedback | fail | 3 | — | — | 64k | 2026-06-23 |
| qwen3.5-2b | baseline | fail | 1 | 95.7 | 4.1s | 64k | 2026-07-02 |
| qwen3.5-4b | baseline | fail | 1 | 44.1 | 21.7s | 64k | 2026-07-02 |
| qwen3.5-0.8b | baseline | fail | 1 | 175.3 | 2.7s | 64k | 2026-07-02 |
Transcripts
gemma-4-26b-a4b-it · bare · PASS
```python
def wildcard_match(s: str, pattern: str) -> bool:
"""
Determines if the string 's' matches the 'pattern'.
'?' matches any single character.
'*' matches any sequence of characters (including empty).
"""
s_len = len(s)
p_len = len(pattern)
# s_idx tracks position in string, p_idx tracks position in pattern
s_idx = 0
p_idx = 0
# star_idx tracks the last encountered '*' position in pattern
star_idx = -1
# match_idx tracks the position in s that was matched by the last '*'
match_idx = 0
while s_idx < s_len:
# Case 1: Characters match or pattern has '?'
if p_idx < p_len and (pattern[p_idx] == '?' or pattern[p_idx] == s[s_idx]):
s_idx += 1
p_idx += 1
# Case 2: Pattern has '*'
elif p_idx < p_len and pattern[p_idx] == '*':
star_idx = p_idx
match_idx = s_idx
p_idx += 1
# Case 3: Current characters don't match, but we encountered a '*' previously
elif star_idx != -1:
# Backtrack: move to the next character in 's' to try matching with the last '*'
p_idx = star_idx + 1
match_idx += 1
s_idx = match_idx
# Case 4: No match and no previous '*' to backtrack to
else:
return False
# Check if remaining characters in pattern are all '*'
while p_idx < p_len and pattern[p_idx] == '*':
p_idx += 1
return p_idx == p_len
if __name__ == "__main__":
# Test cases
assert wildcard_match("aa", "a") == False
assert wildcard_match("aa", "*") == True
assert wildcard_match("cb", "?a") == False
assert wildcard_match("adceb", "*a*b") == True
assert wildcard_match("acdcb", "a*c?b") == False
assert wildcard_match("", "***") == True
assert wildcard_match("abcde", "a*e") == True
print("All tests passed!")
```gemma-4-26b-a4b-it · dev_cycle · PASS
```python
def wildcard_match(s: str, pattern: str) -> bool:
"""
Determines if the string 's' matches the 'pattern'.
'?' matches any single character.
'*' matches any sequence of characters (including empty).
"""
s_len = len(s)
p_len = len(pattern)
# s_idx tracks position in string, p_idx tracks position in pattern
s_idx = 0
p_idx = 0
# star_idx tracks the last encountered '*' position in pattern
star_idx = -1
# match_idx tracks the position in s that was matched by the last '*'
match_idx = 0
while s_idx < s_len:
# Case 1: Characters match or pattern has '?'
if p_idx < p_len and (pattern[p_idx] == '?' or pattern[p_idx] == s[s_idx]):
s_idx += 1
p_idx += 1
# Case 2: Pattern has '*'
elif p_idx < p_len and pattern[p_idx] == '*':
star_idx = p_idx
match_idx = s_idx
p_idx += 1
# Case 3: Current characters don't match, but we encountered a '*' previously
elif star_idx != -1:
# Backtrack: move to the next character in 's' to try matching with the last '*'
p_idx = star_idx + 1
match_idx += 1
s_idx = match_idx
# Case 4: No match and no previous '*' to backtrack to
else:
return False
# Check if remaining characters in pattern are all '*'
while p_idx < p_len and pattern[p_idx] == '*':
p_idx += 1
return p_idx == p_len
if __name__ == "__main__":
# Test cases
assert wildcard_match("aa", "a") == False
assert wildcard_match("aa", "*") == True
assert wildcard_match("cb", "?a") == False
assert wildcard_match("adceb", "*a*b") == True
assert wildcard_match("acdcb", "a*c?b") == False
assert wildcard_match("", "***") == True
assert wildcard_match("abcde", "a*e") == True
print("All tests passed!")
```gpt-oss-120b · baseline · PASS
```python
def wildcard_match(s: str, pattern: str) -> bool:
"""
Returns True if the entire string `s` matches the given `pattern`.
Pattern syntax:
? - matches any single character
* - matches any sequence of characters (including empty)
other characters match themselves literally.
"""
# DP with two rows to save space
n, m = len(s), len(pattern)
prev = [False] * (m + 1)
curr = [False] * (m + 1)
# Empty pattern matches empty string
prev[0] = True
# Initialize first row for empty s (i=0)
for j in range(1, m + 1):
if pattern[j - 1] == '*':
prev[j] = prev[j - 1]
else:
prev[j] = False
for i in range(1, n + 1):
curr[0] = False # non‑empty s cannot match empty pattern
for j in range(1, m + 1):
p_char = pattern[j - 1]
if p_char == '*':
# * matches zero chars (prev[j-1]) or one+ chars (curr[j-1])
curr[j] = prev[j] or curr[j - 1]
elif p_char == '?' or p_char == s[i - 1]:
curr[j] = prev[j - 1]
else:
curr[j] = False
# swap rows for next iteration
prev, curr = curr, prev
return prev[m]
# Export name for import compatibility
__all__ = ["wildcard_match"]
```llama-3.3-70b · baseline · PASS
```python
def wildcard_match(s: str, pattern: str) -> bool:
"""
Returns True if the given pattern matches the entire string s.
The pattern can contain two special characters:
- '?' matches any single character
- '*' matches any sequence of characters (including an empty sequence)
All other characters in the pattern match themselves literally.
"""
dp = [[False] * (len(pattern) + 1) for _ in range(len(s) + 1)]
# An empty pattern can only match an empty string
dp[0][0] = True
# If the pattern starts with '*', it can also match an empty string
for j in range(1, len(pattern) + 1):
if pattern[j - 1] == '*':
dp[0][j] = dp[0][j - 1]
# Fill up the rest of the table
for i in range(1, len(s) + 1):
for j in range(1, len(pattern) + 1):
if pattern[j - 1] == '*':
# '*' can match any sequence of characters (including an empty sequence)
dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
else:
# '?' matches any single character, all other characters match themselves literally
dp[i][j] = dp[i - 1][j - 1] and (pattern[j - 1] == s[i - 1] or pattern[j - 1] == '?')
return dp[len(s)][len(pattern)]
```qwen3.6-35b-a3b · bare · PASS
```python
def wildcard_match(s, pattern):
i, j = 0, 0
star_idx = -1
s_idx = -1
while i < len(s):
if j < len(pattern) and (pattern[j] == '?' or pattern[j] == s[i]):
i += 1
j += 1
elif j < len(pattern) and pattern[j] == '*':
star_idx = j
s_idx = i
j += 1
elif star_idx != -1:
j = star_idx + 1
s_idx += 1
i = s_idx
else:
return False
while j < len(pattern) and pattern[j] == '*':
j += 1
return j == len(pattern)
```qwen3.6-35b-a3b · dev_cycle · PASS
```python
def wildcard_match(s, pattern):
i, j = 0, 0
star_idx = -1
s_idx = -1
while i < len(s):
if j < len(pattern) and (pattern[j] == '?' or pattern[j] == s[i]):
i += 1
j += 1
elif j < len(pattern) and pattern[j] == '*':
star_idx = j
s_idx = i
j += 1
elif star_idx != -1:
j = star_idx + 1
s_idx += 1
i = s_idx
else:
return False
while j < len(pattern) and pattern[j] == '*':
j += 1
return j == len(pattern)
```devstral-small-2-2512 · baseline · PASS
```python
def wildcard_match(s: str, pattern: str) -> bool:
s_len, p_len = len(s), len(pattern)
dp = [[False] * (p_len + 1) for _ in range(s_len + 1)]
dp[0][0] = True
for j in range(1, p_len + 1):
if pattern[j - 1] == '*':
dp[0][j] = dp[0][j - 1]
for i in range(1, s_len + 1):
for j in range(1, p_len + 1):
if pattern[j - 1] == '?':
dp[i][j] = dp[i - 1][j - 1]
elif pattern[j - 1] == '*':
dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
else:
dp[i][j] = dp[i - 1][j - 1] and (s[i - 1] == pattern[j - 1])
return dp[s_len][p_len]
```mistral-small-3.1-24b-instruct-2503 · baseline · PASS
```python
def wildcard_match(s: str, pattern: str) -> bool:
s_len, p_len = len(s), len(pattern)
dp = [[False] * (p_len + 1) for _ in range(s_len + 1)]
dp[0][0] = True
for j in range(1, p_len + 1):
if pattern[j - 1] == '*':
dp[0][j] = dp[0][j - 1]
for i in range(1, s_len + 1):
for j in range(1, p_len + 1):
if pattern[j - 1] == '*':
dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
elif pattern[j - 1] == '?' or s[i - 1] == pattern[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
return dp[s_len][p_len]
if __name__ == "__main__":
import doctest
doctest.testmod()
```qwen3.5-122b-a10b-cluster · baseline · PASS
```python
def wildcard_match(s, pattern):
s_len = len(s)
p_len = len(pattern)
s_idx = 0
p_idx = 0
star_idx = -1
match_idx = -1
while s_idx < s_len:
if p_idx < p_len and (pattern[p_idx] == '?' or pattern[p_idx] == s[s_idx]):
s_idx += 1
p_idx += 1
elif p_idx < p_len and pattern[p_idx] == '*':
star_idx = p_idx
match_idx = s_idx
p_idx += 1
elif star_idx != -1:
p_idx = star_idx + 1
match_idx += 1
s_idx = match_idx
else:
return False
while p_idx < p_len and pattern[p_idx] == '*':
p_idx += 1
return p_idx == p_len
```gpt-oss-20b · baseline · PASS
```python
def wildcard_match(s, pattern):
"""
Return True iff the entire string `s` matches the wildcard `pattern`.
'?' matches any single character.
'*' matches any sequence of characters (including empty).
All other characters match themselves literally.
"""
if s is None or pattern is None:
return False
n, m = len(s), len(pattern)
# dp[i][j] : whether s[:i] matches pattern[:j]
dp = [[False] * (m + 1) for _ in range(n + 1)]
dp[0][0] = True
# Initialize first row: empty string vs pattern prefixes
for j in range(1, m + 1):
if pattern[j - 1] == '*':
dp[0][j] = dp[0][j - 1]
else:
break
for i in range(1, n + 1):
for j in range(1, m + 1):
p_char = pattern[j - 1]
s_char = s[i - 1]
if p_char == '*':
# '*' matches empty (dp[i][j-1]) or one more char (dp[i-1][j])
dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
elif p_char == '?' or p_char == s_char:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = False
return dp[n][m]
```qwen3-coder-30b · baseline · PASS
```python
def wildcard_match(s, pattern):
"""
Match a string against a wildcard pattern.
? matches any single character
* matches any sequence of characters (including empty sequence)
Other characters match themselves literally
Args:
s (str): The string to match
pattern (str): The pattern to match against
Returns:
bool: True if pattern matches the entire string s
"""
# Memoization cache
memo = {}
def helper(i, j):
# If we've already computed this result, return it
if (i, j) in memo:
return memo[(i, j)]
# If we've reached the end of the pattern
if j == len(pattern):
# We match only if we've also reached the end of the string
result = i == len(s)
elif pattern[j] == '*':
# * can match empty sequence or one more character
# Try both options: skip * or match one character and keep *
result = helper(i, j + 1) or (i < len(s) and helper(i + 1, j))
elif i < len(s) and (pattern[j] == '?' or pattern[j] == s[i]):
# Single character match or ? wildcard
result = helper(i + 1, j + 1)
else:
# No match
result = False
memo[(i, j)] = result
return result
return helper(0, 0)
```gemma-4-26b-a4b-it · baseline · PASS
```python
def wildcard_match(s: str, pattern: str) -> bool:
"""
Determines if the string 's' matches the 'pattern'.
'?' matches any single character.
'*' matches any sequence of characters (including empty).
"""
s_len = len(s)
p_len = len(pattern)
# s_idx tracks position in string, p_idx tracks position in pattern
s_idx = 0
p_idx = 0
# star_idx tracks the last encountered '*' position in pattern
star_idx = -1
# match_idx tracks the position in s that was matched by the last '*'
match_idx = 0
while s_idx < s_len:
# Case 1: Characters match or pattern has '?'
if p_idx < p_len and (pattern[p_idx] == '?' or pattern[p_idx] == s[s_idx]):
s_idx += 1
p_idx += 1
# Case 2: Pattern has '*'
elif p_idx < p_len and pattern[p_idx] == '*':
star_idx = p_idx
match_idx = s_idx
p_idx += 1
# Case 3: Current characters don't match, but we encountered a '*' previously
elif star_idx != -1:
# Backtrack: move to the next character in 's' to try matching with the last '*'
p_idx = star_idx + 1
match_idx += 1
s_idx = match_idx
# Case 4: No match and no previous '*' to backtrack to
else:
return False
# Check if remaining characters in pattern are all '*'
while p_idx < p_len and pattern[p_idx] == '*':
p_idx += 1
return p_idx == p_len
if __name__ == "__main__":
# Test cases
assert wildcard_match("aa", "a") == False
assert wildcard_match("aa", "*") == True
assert wildcard_match("cb", "?a") == False
assert wildcard_match("adceb", "*a*b") == True
assert wildcard_match("acdcb", "a*c?b") == False
assert wildcard_match("", "***") == True
assert wildcard_match("abcde", "a*e") == True
print("All tests passed!")
```qwen3.6-35b-a3b-or · baseline · PASS
```python
def wildcard_match(s: str, pattern: str) -> bool:
m, n = len(s), len(pattern)
dp = [False] * (n + 1)
dp[0] = True
for j in range(1, n + 1):
if pattern[j-1] == '*':
dp[j] = dp[j-1]
for i in range(1, m + 1):
prev = dp[0]
dp[0] = False
for j in range(1, n + 1):
temp = dp[j]
if pattern[j-1] == '?' or pattern[j-1] == s[i-1]:
dp[j] = prev
elif pattern[j-1] == '*':
dp[j] = dp[j] or dp[j-1]
else:
dp[j] = False
prev = temp
return dp[n]
```gemini-2.5-flash-lite · baseline · PASS
```python
def wildcard_match(s: str, pattern: str) -> bool:
"""
Checks if a pattern with wildcards matches a string.
Args:
s: The input string.
pattern: The pattern string with '*' and '?' wildcards.
Returns:
True if the pattern matches the entire string, False otherwise.
"""
n = len(s)
m = len(pattern)
# dp[i][j] will be True if the first i characters of s match the first j characters of pattern
dp = [[False] * (m + 1) for _ in range(n + 1)]
# Base case: empty string matches empty pattern
dp[0][0] = True
# Handle patterns starting with '*'
for j in range(1, m + 1):
if pattern[j - 1] == '*':
dp[0][j] = dp[0][j - 1]
# Fill the DP table
for i in range(1, n + 1):
for j in range(1, m + 1):
if pattern[j - 1] == '*':
# '*' can match an empty sequence (dp[i][j-1]) or
# match one or more characters (dp[i-1][j])
dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
elif pattern[j - 1] == '?' or s[i - 1] == pattern[j - 1]:
# '?' matches any single character, or characters match literally
dp[i][j] = dp[i - 1][j - 1]
else:
# Characters don't match and it's not a wildcard
dp[i][j] = False
return dp[n][m]
```qwen3.6-35b-bf16 · baseline · PASS
```python
def wildcard_match(s, pattern):
m, n = len(s), len(pattern)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for j in range(1, n + 1):
if pattern[j-1] == '*':
dp[0][j] = dp[0][j-1]
for i in range(1, m + 1):
for j in range(1, n + 1):
if pattern[j-1] != '*':
dp[i][j] = dp[i-1][j-1] and (pattern[j-1] == '?' or pattern[j-1] == s[i-1])
else:
dp[i][j] = dp[i-1][j] or dp[i][j-1]
return dp[m][n]
```granite-4.1-30b · baseline · PASS
```python
def wildcard_match(s: str, pattern: str) -> bool:
m, n = len(s), len(pattern)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for j in range(1, n + 1):
if pattern[j - 1] == '*':
dp[0][j] = dp[0][j - 1]
for i in range(1, m + 1):
for j in range(1, n + 1):
if pattern[j - 1] == '*':
dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
elif pattern[j - 1] == '?' or s[i - 1] == pattern[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
return dp[m][n]
```qwen3.6-27b · v1.7.1 · PASS
```python
def wildcard_match(s: str, pattern: str) -> bool:
"""
Returns True if pattern matches the entire string s.
'?' matches any single character.
'*' matches any sequence of characters (including empty).
Other characters match literally.
"""
m = len(s)
n = len(pattern)
# dp[i][j] will be True if s[0..i-1] matches pattern[0..j-1]
dp = [[False] * (n + 1) for _ in range(m + 1)]
# Empty string matches empty pattern
dp[0][0] = True
# Handle patterns starting with '*' which can match empty sequence
for j in range(1, n + 1):
if pattern[j - 1] == '*':
dp[0][j] = dp[0][j - 1]
for i in range(1, m + 1):
for j in range(1, n + 1):
if pattern[j - 1] == '*':
# '*' can match empty sequence (dp[i][j-1])
# or any character followed by the rest of the string (dp[i-1][j])
dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
elif pattern[j - 1] == '?' or pattern[j - 1] == s[i - 1]:
# Current characters match, check previous state
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = False
return dp[m][n]
```qwen3-next-80b · baseline · PASS
```python
def wildcard_match(s, pattern):
m, n = len(s), len(pattern)
# dp[i][j] represents whether s[:i] matches pattern[:j]
dp = [[False] * (n + 1) for _ in range(m + 1)]
# Empty string matches empty pattern
dp[0][0] = True
# Handle patterns that start with '*' which can match empty string
for j in range(1, n + 1):
if pattern[j - 1] == '*':
dp[0][j] = dp[0][j - 1]
# Fill the DP table
for i in range(1, m + 1):
for j in range(1, n + 1):
if pattern[j - 1] == '*':
# '*' can match zero characters (dp[i][j-1]) or one or more characters (dp[i-1][j])
dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
elif pattern[j - 1] == '?' or pattern[j - 1] == s[i - 1]:
# '?' matches any single char, or exact character match
dp[i][j] = dp[i - 1][j - 1]
return dp[m][n]
```phi-4-reasoning-plus · baseline · PASS
We are asked: "Implement `wildcard_match(s, pattern)` returning True iff `pattern` matches the ENTIRE string `s`. `?` matches any single character; `*` matches any sequence of characters including the empty sequence; every other character matches itself literally. Importable as `from solution import wildcard_match`." We need to produce a Python code block that is self-contained and can be imported from "solution" module.
We are asked: "Implement wildcard_match(s, pattern)" returning True if pattern matches entire string s. The matching rules: '?' matches any single character; '*' matches any sequence of characters including empty sequence; every other character must match itself literally.
This is a typical wildcard matching problem. We can implement using dynamic programming or recursion with memoization. But the simplest solution is to use recursion with caching, but careful with performance if s and pattern are long. Alternatively, we can use iterative DP algorithm. I'll produce a self-contained Python code block that defines wildcard_match(s, pattern) function.
I need to produce a single python code block with no explanation before or after. The instructions: "Output a single self-contained Python solution as one ```python code block, with no explanation before or after." So I must output a code block starting with triple backticks and language python, then the code, then triple backticks.
I'll produce a function wildcard_match(s, pattern) that returns True if pattern matches entire string s. We can use recursion with memoization. Alternatively, we can use iterative DP algorithm. Let's consider both approaches:
Approach 1: Recursion with caching:
Define helper(i, j) where i is index in s and j is index in pattern. If j equals len(pattern), then return i equals len(s). Otherwise if pattern[j] equals '*' then try to match zero or more characters by either consuming star (i.e., skip the star) or consuming one character from s if available. But careful: if we use recursion, it might be exponential time if not memoized.
I can do:
```
def wildcard_match(s, pattern):
memo = {}
def dp(i, j):
if (i, j) in memo:
return memo[(i,j)]
if j == len(pattern):
ans = i == len(s)
else:
if pattern[j] == '*':
# either skip star or consume one char from s
ans = dp(i, j+1) or (i < len(s) and dp(i+1, j))
else:
# must match exactly: if pattern[j]=='?' then any char, otherwise literal equals.
if i < len(s) and (pattern[j] == '?' or pattern[j] == s[i]):
ans = dp(i+1, j+1)
else:
ans = False
memo[(i,j)] = ans
return ans
return dp(0, 0)
```
That is a valid solution.
Alternatively, we can use iterative DP algorithm. But I'll produce recursion with caching because it's simpler to code and easier to read.
I must also include "if __name__ == '__main__':" block for testing? The instructions say: "Implement wildcard_match(s, pattern) returning True iff pattern matches the ENTIRE string s." It says "importable as from solution import wildcard_match". So I need to produce a module that defines wildcard_match. But it's not necessary to include main test code if not required.
I can produce a self-contained Python file with function definition and maybe some tests in __main__ block, but instructions say: "Output a single self-contained Python solution as one ```python code block, with no explanation before or after." So I'll produce a code block that defines wildcard_match. Possibly also include if __name__ == '__main__': to run some test cases.
But the instruction says "importable as from solution import wildcard_match", so it's expected that the module is named "solution.py". But we can simply output the function definition and then maybe add a main block with tests commented out. But instructions say no explanation before or after, so I'll produce code block with only code.
I must produce a single python code block with triple backticks and language python. The code should be self-contained.
I'll produce:
```
def wildcard_match(s, pattern):
memo = {}
def dp(i, j):
if (i, j) in memo:
return memo[(i, j)]
if j == len(pattern):
result = (i == len(s))
else:
if pattern[j] == '*':
# either use star to match empty sequence or one char from s
result = dp(i, j+1) or (i < len(s) and dp(i+1, j))
else:
if i < len(s) and (pattern[j] == '?' or pattern[j] == s[i]):
result = dp(i+1, j+1)
else:
result = False
memo[(i, j)] = result
return result
return dp(0, 0)
if __name__ == '__main__':
# Some test cases
tests = [
("", ""),
("", "*"),
("*", ""),
("abc", "a*c"), # True: a matches 'a', * matches "b", c matches "c"
("abcd", "a?cd"), # True: a matches, ? matches b, cd literal
("abcd", "a*d"), # False: a matches, * matches "bcd" but then d doesn't match?
("hello world", "he*o w*rld"),
("abcdef", "*b*d"), # True: star matches "ac", then b matches letter b? Let's check: pattern = "*b*d". s = "abcdef"
]
for s, pat in tests:
print(f"wildcard_match({s!r}, {pat!r}) -> {wildcard_match(s, pat)}")
```
Wait, let me re-check test cases:
Test case 1: ("", "") should return True because empty pattern matches empty string.
Test case 2: ("", "*") returns True because star can match empty sequence.
Test case 3: ("*", "") returns False because pattern is not empty but s is "*", and no wildcard in pattern to match it. But wait, if pattern is "*" then it should match entire string "abc"? Actually test case 3: ("*", "") means s = "*" and pattern = "", that's false because pattern doesn't have any charadeepseek-r1-distill-qwen-32b · baseline · PASS
To solve this problem, we need to implement a function `wildcard_match(s, pattern)` that returns True if and only if the entire string `s` matches the given `pattern`. The pattern can include special characters '?' and '*', which have specific meanings.
### Approach
The approach to solving this problem involves using dynamic programming (DP) to efficiently check for a match between the string `s` and the pattern. Here's a detailed breakdown of the steps:
1. **Dynamic Programming Table Initialization**: We create a 2D DP table where `dp[i][j]` indicates whether the substring `s[0:i]` matches the pattern `pattern[0:j]`. The dimensions of this table are `(len(s)+1) x (len(pattern)+1)`.
2. **Base Cases**:
- If both the string and pattern are empty, they match (`dp[0][0] = True`).
- An empty string can only match a pattern that starts with '*' followed by other characters, but this is handled in subsequent steps.
3. **Filling the DP Table**:
- For each character in the string `s` and each character in the pattern `pattern`, we update the DP table based on the current characters.
- If the current pattern character is '?', it matches any single character, so we check if the previous characters matched (`dp[i-1][j-1]`).
- If the current pattern character is '*', it can match zero or more of any character. Thus, we check if either the substring without this '*' (i.e., `dp[i][j-1]`) matches, or if the '*' matches one or more characters from the string (`dp[i-1][j]`).
- For other characters, they must match exactly between the string and pattern.
4. **Edge Cases Handling**: Special handling is done for cases where the pattern starts with '*' to ensure that it can match an empty string or any sequence of characters.
### Solution Code
```python
def wildcard_match(s, pattern):
m = len(s)
n = len(pattern)
# Create a DP table with (m+1) rows and (n+1) columns.
dp = [[False] * (n + 1) for _ in range(m + 1)]
# Base case: empty string matches empty pattern
dp[0][0] = True
# Handle the case where pattern starts with '*'
for j in range(1, n + 1):
if pattern[j-1] == '*' and dp[0][j-1]:
dp[0][j] = True
# Fill the DP table
for i in range(1, m + 1):
for j in range(1, n + 1):
if pattern[j-1] == '?':
dp[i][j] = dp[i-1][j-1]
elif pattern[j-1] == '*':
# '*' can match zero or more characters
dp[i][j] = dp[i][j-1] or (dp[i-1][j] if s[i-1] else False)
else:
dp[i][j] = dp[i-1][j-1] and (s[i-1] == pattern[j-1])
return dp[m][n]
```
### Explanation
The solution uses dynamic programming to efficiently determine if the string `s` matches the given `pattern`. The DP table is built by iterating through each character of both the string and the pattern, updating the table based on whether the current characters match according to the rules defined for '?' and '*'. This approach ensures that all possible ways of matching are considered, leading to an accurate result.qwen3.6-35b-a3b · baseline · PASS
```python
def wildcard_match(s: str, pattern: str) -> bool:
"""
Match string s against pattern where:
- '?' matches any single character
- '*' matches any sequence of characters (including empty)
- other characters match literally
Returns True if pattern matches the ENTIRE string s.
"""
# Use dynamic programming approach
m, n = len(s), len(pattern)
# dp[i][j] means whether s[:i] matches pattern[:j]
dp = [[False] * (n + 1) for _ in range(m + 1)]
# Empty string matches empty pattern
dp[0][0] = True
# Handle patterns with leading '*' characters matching empty prefix of s
for j in range(1, n + 1):
if pattern[j - 1] == '*':
dp[0][j] = dp[0][j - 1]
for i in range(1, m + 1):
for j in range(1, n + 1):
if pattern[j - 1] == '*':
# '*' can match zero characters (dp[i][j-1]) or one more character (dp[i-1][j])
dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
elif pattern[j - 1] == '?' or pattern[j - 1] == s[i - 1]:
# Current characters match, check previous state
dp[i][j] = dp[i - 1][j - 1]
return dp[m][n]
```qwen3.6-27b · baseline · PASS
```python
def wildcard_match(s: str, pattern: str) -> bool:
"""
Returns True if pattern matches the entire string s.
'?' matches any single character.
'*' matches any sequence of characters (including empty).
Other characters match literally.
"""
m = len(s)
n = len(pattern)
# dp[i][j] will be True if s[0..i-1] matches pattern[0..j-1]
dp = [[False] * (n + 1) for _ in range(m + 1)]
# Empty string matches empty pattern
dp[0][0] = True
# Handle patterns starting with '*' which can match empty sequence
for j in range(1, n + 1):
if pattern[j - 1] == '*':
dp[0][j] = dp[0][j - 1]
for i in range(1, m + 1):
for j in range(1, n + 1):
if pattern[j - 1] == '*':
# '*' can match empty sequence (dp[i][j-1])
# or any character followed by the rest of the string (dp[i-1][j])
dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
elif pattern[j - 1] == '?' or pattern[j - 1] == s[i - 1]:
# Current characters match, check previous state
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = False
return dp[m][n]
```claude-sonnet-4.6 · baseline · PASS
```python
def wildcard_match(s: str, pattern: str) -> bool:
m, n = len(s), len(pattern)
# dp[i][j] = True if pattern[:j] matches s[:i]
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
# Handle patterns like *** at the start
for j in range(1, n + 1):
if pattern[j - 1] == '*':
dp[0][j] = dp[0][j - 1]
else:
break
for i in range(1, m + 1):
for j in range(1, n + 1):
c = pattern[j - 1]
if c == '*':
# '*' matches empty sequence: dp[i][j-1]
# '*' matches one more char: dp[i-1][j]
dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
elif c == '?' or c == s[i - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = False
return dp[m][n]
```granite-4.1-8b · baseline · fail
```python
def wildcard_match(s: str, pattern: str) -> bool:
def dp(i: int, j: int) -> bool:
if j == len(pattern):
return i == len(s)
first_match = (i < len(s)) and (pattern[j] in {s[i], '?'})
if j + 1 < len(pattern) and pattern[j + 1] == '*':
return dp(i, j + 2) or (first_match and dp(i + 1, j))
return first_match and dp(i + 1, j + 1)
return dp(0, 0)
```qwen3.5-2b · baseline · fail
```python
def wildcard_match(s: str, pattern: str) -> bool:
"""
Returns True iff pattern matches the entire string s.
- '?' matches any single character.
- '*' matches any sequence of characters (including empty).
- Every other character matches itself literally.
"""
n = len(s)
m = len(pattern)
# Precompute lengths for each position in pattern:
# dp[i][j] = length of the longest prefix of s that is a suffix of pattern[0:i].
# This allows us to check if we can match the remaining characters.
dp = [[0] * (m + 1) for _ in range(n + 1)]
# Base case: empty string matches any prefix of pattern
for i in range(m + 1):
dp[0][i] = 0
# Fill the DP table
for i in range(1, n + 1):
for j in range(1, m + 1):
if s[i - 1] == pattern[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
# If characters don't match, we can only extend the previous row's length
# by taking the maximum of (dp[i-1][j], dp[i][j-1])
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
# Check if pattern matches entire string s:
# The last character of s must match the last character of pattern,
# and we need to have matched all characters.
return dp[n][m] == n
```qwen3.5-4b · baseline · fail
```python
def wildcard_match(s, pattern):
m, n = len(pattern), len(s)
# dp[i][j] means pattern[0:j] matches s[0:i]
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
# Handle empty string matching with wildcards at start of pattern
for j in range(1, m + 1):
if pattern[j-1] == '*':
dp[0][j] = dp[0][j-1]
# Fill the DP table
for i in range(1, n + 1):
for j in range(1, m + 1):
if pattern[j-1] == '?':
dp[i][j] = dp[i-1][j-1]
elif pattern[j-1] == '*':
dp[i][j] = dp[i][j-1] or dp[i-1][j]
else:
dp[i][j] = (pattern[j-1] == s[i-1]) and dp[i-1][j-1]
return dp[n][m]
```qwen3.5-0.8b · baseline · fail
```python
def wildcard_match(s: str, pattern: str) -> bool:
"""
Check if pattern matches the entire string s.
Rules:
- '?' matches any single character (including empty sequence).
- '*' matches any sequence of characters including the empty sequence.
- Every other character matches itself literally.
Returns True iff pattern matches the ENTIRE string s.
"""
if len(s) == 0 or len(pattern) == 0:
return False
# Count occurrences of each character in both strings
char_counts = {}
for c in s:
char_counts[c] = char_counts.get(c, 0) + 1
pattern_char_counts = {}
for p_char in pattern:
if p_char == '?':
# '?' matches any single character (including empty sequence)
pass
elif p_char == '*':
# '*' matches any sequence of characters including the empty sequence
# We need to check if there are enough occurrences of this char in s
count = 0
for c in s:
if c == p_char:
count += 1
break
else:
# Other chars match literally
pattern_char_counts[p_char] = pattern_char_counts.get(p_char, 0) + 1
# If the counts don't match, return False
for char in s:
if char not in pattern_char_counts or pattern_char_counts[char] != char_counts[char]:
return False
# All characters matched and counts are equal -> True
return True
# Example usage:
if __name__ == "__main__":
print(wildcard_match("a*b", "ab*")) # True (matches 'a' then '*' matches 'b')
print(wildcard_match("abc", "a?c")) # True
print(wildcard_match("", "") # False
print(wildcard_match("aa", "a*a")) # True
print(wildcard_match("ab", "*")) # True (matches 'a' then '*' matches 'b')
```