leetcode-regular-expression-matching.py

class Solution:
    EPLISON_TOKEN = "&"
    FINAL_TOKEN = "$"
    def __init__(self):
        self.states = [
            # [ [char, ID], [char, ID], ...   ]
        ]
        self.s = ""

    def search(self, s_start, state_idx) -> bool:
        for match_char, next_id in self.states[state_idx]:
            if match_char == self.FINAL_TOKEN:
                print(f'{s_start=}')
                return s_start == len(self.s)
            
            if match_char == self.EPLISON_TOKEN:
                if self.search(s_start, next_id):
                    return True
            
            if s_start < len(self.s) and (match_char == self.s[s_start] or match_char == "."):
                if self.search(s_start + 1, next_id):
                    return True
            
        return False


    def isMatch(self, s: str, p: str) -> bool:
        p += self.FINAL_TOKEN
        self.s = s
        
        patterns = [
            # [char: str, is_star: bool]
        ]
        
        for c in p:
            if c == "*":
                patterns[-1][1] = True
            else:
                patterns.append([c, False])
        
        keep_list = []
        for i, pat in enumerate(patterns):
            if tuple(pat) != tuple(patterns[i-1]) or not pat[1]: # duplcated * patterns
                keep_list.append(tuple(pat))


        patterns = keep_list
        
        print(f"{patterns=}")
        
        for i, pat in enumerate(patterns):
            if pat[1]:
                # consruct c -> self, c -> next, eplison -> next
                self.states.append([
                    [pat[0], i],
                    [pat[0], i+1],
                    [self.EPLISON_TOKEN, i+1],
                ])
            else:
                # construct c -> next
                self.states.append([
                    [pat[0], i+1],
                ])

        print(f"{self.states=}")
        return self.search(0, 0)