20. Parentesi valide Dato una stringa s contenente solo i caratteri '(', ')', '{', '}', '[' e ']', determina se la stringa di input è valida. Una stringa di input è valida se: 1. Le parentesi aperte devono essere chiuse con lo stesso tipo di parentesi. 2. Le parentesi aperte devono essere chiuse nell'ordine corretto. 3. Ogni parentesi di chiusura ha una parentesi aperta corrispondente dello stesso tipo. Esempio 1: Input: s = "()" Output: true Esempio 2: Input: s = "()[]{}" Output: true Esempio 3: Input: s = "(]" Output: false

Для проверки валидности строки с скобками удобно использовать стек. Идея:

• Проходим по символам строки.
• Если символ — открывающая скобка, кладём её в стек.
• Если закрывающая — проверяем, что верхний элемент стека соответствует ей по типу.
• Если нет соответствия или стек пуст, строка невалидна.
• В конце стек должен быть пустым.

Пример на Python:

def isValid(s):
    stack = []
    pairs = {')': '(', '}': '{', ']': '['}
    for char in s:
        if char in '([{':
            stack.append(char)
        elif char in ')]}':
            if not stack or stack.pop() != pairs[char]:
                return False
    return not stack

# Примеры
print(isValid("()"))      # True
print(isValid("()[]{}"))  # True
print(isValid("(]"))      # False