# My crappy iterative python solution that took way too long to write

• ``````class Solution(object):
def isMatch(self, s, p):
p = self.cleanPattern(p)
sub_p = p.split('*')
if len(sub_p) == 1: return self.naiveMatch(s, sub_p[0])

s_idx = 0
if sub_p[0] != '':  # if first sub_p is not a wildcard, the beginning string must be a full match w/ first pattern
curr_p = sub_p.pop(0)
pattern_len = len(curr_p)
if (len(s) < pattern_len) or (self.naiveMatch(s[:pattern_len], curr_p)):
return False
s_idx = pattern_len

while len(sub_p) > 0:
curr_p = sub_p.pop(0)
pattern_len = len(curr_p)
if len(sub_p) != 0:

while True:
if pattern_len + s_idx > len(s):
return False
sub_s = s[s_idx:s_idx+pattern_len]
if self.naiveMatch(sub_s, curr_p)
s_idx += pattern_len
break
s_idx += 1
else:
# match from backwards
if len(s)-pattern_len < s_idx:
return False

sub_s = s[len(s)-pattern_len:]
return self.naiveMatch(sub_s, curr_p)
return True

def naiveMatch(self, s, pattern):
# where pattern contains no *
if len(pattern) != len(s):
return False
for i in xrange(len(s)):
if pattern[i] != '?' and pattern[i] != s[i]:
return False
return True

def cleanPattern(self, p):
# remove shit like '***'
new_p = ''
i = 0
while i < len(p):
ch = p[i]
new_p += ch
i += 1
if ch == '*':
while i < len(p) and p[i] == '*':
i += 1
return new_p

`````````

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