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


  • 0
    A
    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
            
           ```

Log in to reply
 

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