Solution #31a0c389-62b2-4f47-8f6e-f8d8d9b3fc54

def solve(input):
    string = input["string"]
    pattern = input["pattern"]
    
    def match_char(c, p):
        if p == '.':
            return True
        if len(p) == 3 and p[0] == '[' and p[2] == ']':
            if p[1] == '^':
                return c not in p[3:-1]
            else:
                return c in p[1:-1]
        return c == p
    
    def match(s, p):
        if not p:
            return not s
        
        first_match = bool(s) and match_char(s[0], p[0])
        
        if len(p) >= 2 and p[1] in '*+?':
            if p[1] == '*':
                return (first_match and match(s[1:], p)) or match(s, p[2:])
            elif p[1] == '+':
                return first_match and ((first_match and match(s[1:], p)) or match(s[1:], p[2:]))
            elif p[1] == '?':
                return (first_match and match(s[1:], p[2:])) or match(s, p[2:])
        
        if len(p) >= 3 and p[0] == '[':
            i = 1
            if p[i] == '^':
                i += 1
            while i < len(p) and p[i] != ']':
                i += 1
            if i < len(p) and p[i] == ']':
                return first_match and match(s[1:], p[i+1:])
        
        return first_match and match(s[1:], p[1:])
    
    return match(string, pattern)