Algorithm Puzzles: Wildcard Matching

Algorithm Puzzles everyday every week sometimes: Wildcard Matching

Puzzle

Puzzle from leetcode:

Given an input string (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).

The matching should cover the entire input string (not partial).

Solving

Using backtrace:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
def isMatch(self, s: str, p: str) -> bool:
if not s and not p:
return True

si, pi = 0, 0
sl, pl = len(s), len(p)
starIndex, siLast = -1, -1

while si < sl:
if pi < pl and (s[si] == p[pi] or p[pi] == '?'):
si += 1
pi += 1
# Check if * can be used as empty string
elif pi < pl and p[pi] == '*':
siLast = si
starIndex = pi
pi += 1
# Not match but have *. Try s[siLast+1] and p[starIndex+1]
elif starIndex != -1:
siLast += 1
si = siLast
pi = starIndex + 1
else: # Not match and have no *
return False

while pi < pl and p[pi] == '*':
pi += 1

return pi == pl