In questo articolo vedremo una possibile soluzione ad un semplice esercizio di programmazione in Python.
Data una stringa s contenente solo i caratteri '(', ')', '{', '}', '[' e ']', stabilire se la stringa di input è valida.
Una stringa di input è valida se:
- Le parentesi aperte devono essere chiuse dallo stesso tipo di parentesi.
- Le parentesi aperte devono essere chiuse nell'ordine corretto.
- Ogni parentesi chiusa ha una corrispondente parentesi aperta dello stesso tipo.
Esempio 1:
Input: s = "()"
Output: true
Esempio 2:
Input: s = "()[]{}"
Output: true
Esempio 3:
Input: s = "(]"
Output: false
La stringa di input non deve avere più di 104 caratteri e deve essere costituita solo dalle parentesi '()[]{}'.
Si tratta sostanzialmente di effettuare la scansione della stringa carattere per carattere tenendo traccia del carattere corrente e del carattere immediatamente successivo.
def is_valid(s = None):
if s is None:
return False
length_s = len(s)
if length_s == 0 or length_s > 104:
return False
allowed_chars = ['(', ')', '{', '}', '[', ']']
valid = True
for c in s:
if not c in allowed_chars:
valid = False
i = 0
while i < length_s:
ch = s[i]
next_i = i + 1
next_ch = s[next_i] if next_i < length_s else None
if not next_ch:
break
match ch:
case '(':
if next_ch != ')':
valid = False
case '{':
if next_ch != '}':
valid = False
case '[':
if next_ch != ']':
valid = False
case _:
break
i += 1
return valid