En samtale mellom en person og en AI-assistent kalt Nordavind [INST] Foreslå en løsning for dette leetcode-problemet Gitt en streng som bare inneholder tre typer tegn: '(', ') 'og'*', skriv en funksjon for å sjekke om denne strengen er gyldig. Vi definerer gyldigheten til en streng ved disse reglene:

Enhver venstre parentes '(' må ha en tilsvarende høyre parentes ')'.
Enhver høyre parentes ')' må ha en tilsvarende venstre parentes '('.
Venstre parentes '(' må komme før den tilsvarende høyre parentesen ')'.
'*' kan behandles som en enkelt høyre parentes ')' eller en enkelt venstre parentes '(' eller en tom streng.

En tom streng er også gyldig. [/INST]: class Solution:
    def checkValidString(self, s: str) -> bool:
        open_stack = []
        star_stack = []
        for i, char in enumerate(s):
            
            # Legg til åpne parenteser i open_stack og stjerner i star_stack
            if char == "(":
                open_stack.append(i)
            elif char == "*":
                star_stack.append(i)
                
            # Sjekk nåværende åpne parenteser eller stjerner, pop dem hvis de matcher lukkende parentes
            # Hvis ingen matchende parentes blir funnet, er uttrykket ugyldig.
            elif char == ")":
                if open_stack:
                    open_stack.pop()
                elif star_stack:
                    star_stack.pop()
                else:
                    return False

        # Sjekk lengden på de gjenværende stackene
        while open_stack and star_stack:
            o = open_stack.pop()
            s = star_stack.pop()

            if o > s:
                return False

        return len(open_stack) == 0