Valid Parentheses

Q: ¿Cuál es la complejidad temporal de Valid Parentheses?

La solución con pila se ejecuta en tiempo O(n) , ya que cada carácter se inserta o se extrae como máximo una vez. Usa espacio O(n) en el peor de los casos: una cadena formada únicamente por aperturas. Eliminar repetidamente los pares coincidentes lleva tiempo O(n²) , porque una cadena profundamente anidada pierde solo un par en cada ronda.

FácilPila

+10

Se te proporciona una cadena s compuesta únicamente por los caracteres de corchetes (, ), [, ], { y }. Devuelve true cuando los corchetes estén equilibrados: cada corchete de cierre cierra el corchete más reciente que siga abierto, ambos son del mismo tipo y no queda ninguno abierto al final. De lo contrario, devuelve false.

Función

isValid(s: string) → boolean

sstring: la cadena de corchetes que se debe comprobar
Devuelveboolean: si los corchetes están equilibrados

Restricciones

1 ≤ s.length ≤ 10⁴
s contiene solo los caracteres (, ), [, ], { y }.

Ejemplos

Entrada: s = "[]{}()"
Salida: true
Explicación: Tres pares están uno al lado del otro, y cada uno se cierra justo después de abrirse.

Entrada: s = "{(})"
Salida: false
Explicación: El } aparece mientras el ( que se abrió después de él sigue abierto, así que cierra el tipo de corchete equivocado.

Para ir más allá

Si la cadena solo tuviera paréntesis, ¿podrías comprobarla con un único contador en lugar de una pila, usando O(1) de espacio adicional?

Solución

Contar los corchetes no es suficiente: {(}) tiene un corchete de apertura y uno de cierre de cada tipo, y aun así está mal, porque el orden importa. Una pila mantiene los corchetes que siguen abiertos en el orden en que se abrieron, así que una sola pasada con una pila permite determinar si toda la cadena está bien formada.

Eliminar repetidamente los pares coincidentes

Correcto, pero no termina con las pruebas más grandes

Intuición

Toda cadena equilibrada tiene un par más interno sin nada entre sus corchetes, como () dentro de {[()]}. Eliminar un par adyacente que coincide nunca cambia si una cadena está equilibrada. Así que repite las eliminaciones hasta que una ronda no elimine nada: una cadena equilibrada se reduce a vacía, y una no equilibrada se atasca con caracteres restantes, como ocurre desde el principio con {(}).

Cada ronda recorre toda la cadena y construye una copia nueva, y una cadena anidada como (((...))) pierde un par por ronda. Eso supone hasta n/2 rondas de trabajo O(n), O(n²) en total.

Algoritmo

Elimina todos los (), [] y {} de la cadena.
Si en esa ronda no se eliminó nada, detente.
De lo contrario, repite el proceso con la cadena más corta.
Devuelve true si la cadena termina vacía y false si queda algún corchete.

def isValid(s):
    while True:
        # Delete every adjacent matched pair in one round.
        shorter = s.replace("()", "").replace("[]", "").replace("{}", "")
        if shorter == s:
            break  # nothing left to delete
        s = shorter
    return s == ""

Una pasada con una pila

Intuición

Un corchete de cierre debe cerrar el corchete abierto más recientemente que siga abierto. El último corchete que se abre es el primero que se cierra, y ese orden de último en entrar, primero en salir es exactamente lo que mantiene una pila.

Apila el corchete de cierre que espera cada corchete de apertura. Después, un corchete de cierre debe coincidir con la cima de la pila. Una pila vacía significa que no tiene nada que cerrar; una cima distinta significa que cierra el tipo equivocado, como ocurre con } en {(}) mientras ) está en la cima. Al final, cualquier elemento que quede en la pila, como en ((, se abrió y nunca se cerró. Cada carácter se apila o se desapila una vez: tiempo O(n) y, como máximo, n elementos en la pila.

Algoritmo

Crea una pila vacía.
Ante un corchete de apertura, apila su delimitador de cierre correspondiente.
Ante un corchete de cierre, devuelve false si la pila está vacía o si el carácter de la cima es diferente; de lo contrario, desapila.
Después del último carácter, devuelve true solo si la pila está vacía.

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

Errores comunes y casos límite

Contar cada tipo de corchete. {(}) tiene cantidades coincidentes y sigue siendo inválido, y )( falla únicamente por el orden.
Sacar elementos de una pila vacía. Una cadena que empieza con un cierre, como } o )]}, debe devolver false en lugar de provocar un error.
Omitir la comprobación final. (([{ nunca encuentra un cierre incorrecto, así que solo la pila restante revela que es inválida.
Confiar en la longitud. Una longitud impar siempre es inválida, pero una longitud par no demuestra nada: (] y ())( son ambas inválidas.
En el enfoque de eliminación, pasar corchetes a una expresión regular o a un patrón de Lua sin escaparlos. ( y [ tienen un significado allí; usa un reemplazo de texto literal.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de Valid Parentheses?

La solución con pila se ejecuta en tiempo O(n), ya que cada carácter se inserta o se extrae como máximo una vez. Usa espacio O(n) en el peor de los casos: una cadena formada únicamente por aperturas. Eliminar repetidamente los pares coincidentes lleva tiempo O(n²), porque una cadena profundamente anidada pierde solo un par en cada ronda.

¿Por qué se usa una pila para los paréntesis válidos?

Los corchetes se anidan, así que el último corchete abierto debe ser el primero en cerrarse. Una pila mantiene ese corchete en la parte superior, donde puedes leerlo y quitarlo en tiempo constante, lo que mantiene toda la comprobación en O(n).

¿Es válida una cadena vacía como paréntesis?

Sí. Una cadena vacía no tiene ningún corchete sin pareja, así que está equilibrada: la pila permanece vacía y el bucle de eliminación no tiene nada que eliminar. En este problema, s siempre tiene al menos un carácter.

def isValid(s):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumento

s = "[]{}()"

Salida Esperada

true