Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 44 with 24 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 44 # by problem number
lcpy gen -s wildcard_matching # by problem name
s and a pattern p, implement wildcard pattern matching with support for '?' and '*' where:
'?' Matches any single character.'*' Matches any sequence of characters (including the empty sequence).Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Input: s = "aa", p = "*"
Output: true
Explanation: '*' matches any sequence.
Input: s = "cb", p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.
s contains only lowercase English letters.p contains only lowercase English letters, '?' or '*'.class Solution:
# Time: O(s_len * p_len) worst case (star backtracking), Space: O(1)
def is_match(self, s: str, p: str) -> bool:
s_len, p_len = len(s), len(p)
i = j = 0
star_idx = -1
match_idx = 0
while i < s_len:
if j < p_len and (p[j] == "?" or p[j] == s[i]):
i += 1
j += 1
elif j < p_len and p[j] == "*":
star_idx = j
match_idx = i
j += 1
elif star_idx >= 0:
j = star_idx + 1
match_idx += 1
i = match_idx
else:
return False
while j < p_len and p[j] == "*":
j += 1
return j == p_len
| Time | Space |
|---|---|
| O(s_len * p_len) worst case (star backtracking), Space: O(1) | - |