20. Parênteses válidos Dada uma string s que contém apenas os caracteres '(', ')', '{', '}', '[' e ']', determine se a string de entrada é válida. Uma string de entrada é válida se: 1. Os colchetes abertos devem ser fechados pelo mesmo tipo de colchetes. 2. Os colchetes abertos devem ser fechados na ordem correta. 3. Cada colchete de fechamento tem um colchete de abertura correspondente do mesmo tipo. Exemplo 1: Entrada: s = "()" Saída: true Exemplo 2: Entrada: s = "()[]{}" Saída: true Exemplo 3: Entrada: s = "(]" Saída: 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