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


  • 0
    U
    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.


Log in to reply
 

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