# Extend Wildcard Matching O(mn) algorithm by using a stack. Beats 100% python subbmissions.

• ``````def preprocess(self, s):
i = 0
ret = ''
prev_star_chr = None
while i < len(s):
if (i < len(s) - 1) and s[i+1] == '*':
if prev_star_chr is None or prev_star_chr != s[i]:
prev_star_chr = s[i]
ret += s[i:i+2]
i += 2
continue
prev_star_chr = None
ret += s[i]
i += 1
return ret

def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
s_idx = 0
p_idx = 0
p = self.preprocess(p)
last_star_idx_stack = []
while s_idx < len(s):
if p_idx < len(p):
if p_idx < len(p)-1 and p[p_idx+1] == '*':
if p[p_idx] == s[s_idx] or p[p_idx] == '.':
# first match 0 elements
last_star_idx_stack.append((p_idx+1, s_idx))
else:
# This * is of no use to us to match the string.
# Treat it as empty always by not updating the last_* values.
pass

# In both if/else, we treat the * as empty string, so proceed by 2.
p_idx += 2
continue

if s[s_idx] == p[p_idx] or p[p_idx] == '.':
s_idx += 1
p_idx += 1
continue

candidate_found = False
while len(last_star_idx_stack) > 0:
last_star_idx, last_str_unmatched_idx = last_star_idx_stack.pop()
star_chr = p[last_star_idx-1]
s_chr = s[last_str_unmatched_idx]
if star_chr == '.' or star_chr == s_chr:
candidate_found = True
last_str_unmatched_idx += 1
s_idx = last_str_unmatched_idx
p_idx = last_star_idx+1
last_star_idx_stack.append((last_star_idx, s_idx))
break

if candidate_found:
continue

return False

while p_idx < len(p):
if p_idx+1 >= len(p):
return False
if p[p_idx+1] != '*':
return False
p_idx += 2

return True
``````

The one part that seems like a hack is the preprocessing step.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.