Estoy un poco desconcertado por un ejercicio que encontré recientemente.
Parece una tarea fácil y puse mi solución pero resultó que no pasó todas las pruebas :D
En el ejemplo, he encontrado dos subcadenas de ejemplo:
Input: S = "(()(" Output: 2 Explanation: The longest valid substring is "()". Length = 2.y
Input: S = "()(())(" Output: 6 Explanation: The longest valid substring is "()(())". Length = 6.a primera vista, todo está claro.
Se me ocurrió mi solución:
class Solution { findMaxLen(s) { if (!s || !s.length) throw new Error('Invalid input value provided') let openIndex = null let closingIndex = null for (let i = 0; i < s.length; i++) { if (s[i] == '(' && !openIndex) openIndex = i + 1 if (s[i] == ')') closingIndex = i + 1 } if(!closingIndex || !openIndex) throw new Error('Invalid substring') return closingIndex - openIndex + 1 } } Entonces, mi solución debería resolver el problema de tratar de encontrar The longest substring con los paréntesis de apertura y cierre.
Pero falló la prueba con un valor de entrada: (((() Donde la respuesta correcta es 2 y mi salida es 5
¿Es este (((() diferente de ()(())( uno provisto en el ejemplo?)
Supongo que no entiendo del todo la idea de qué es la subcadena o algo así...
Este pseudocódigo debería funcionar. Algunos errores o casos extremos pueden tener cabos sueltos, ya que acabo de escribir esto aquí sobre la marcha. Siéntase libre de probarlo y señalar los fallos.
helper_stack = null max_valid_len = 0 running_len = 0 for i=0 to input_s.length: if helper_stack.length == 0: if input_s[i] == ')': running_len = 0 continue else: helper_stack.push('(') else: if input_s[i] == '(': helper_stack.push('(') else: helper_stack.pop() running_len += 2 if running_len > max_valid_len: max_valid_len = running_len Con su lógica, no está siguiendo el orden de opening and closing de los corchetes, lo cual es importante. Si un closing bracket precede a la apertura, la cadena se vuelve inválida de manera predeterminada. Por lo tanto, usar stack tiene sentido aquí.
Si alguna vez encontramos un paréntesis de cierre antes de abrir, reiniciamos desde ese punto. Por lo tanto, establecemos running_len = 0 . Para cada encuentro de paréntesis de cierre, si hay un paréntesis abierto para equilibrarlo, simplemente lo sacamos, y dado que es un par (de caracteres, cuando consideramos la longitud de la cadena), se running_len += 2 .
Con pocas modificaciones, incluso podemos reproducir max_valid_substring si es necesario. Sin embargo, en nuestro caso, incluso podríamos usar solo un número entero en lugar de helper_stack . Para cada operación push('(') , simplemente haga var += 1 y var -= 1 para pop y eso también debería funcionar. Tenga en cuenta que aquí no estamos usando stack explícitamente, pero esto sigue siendo conceptualmente LIFO = last in first out que es básicamente, apilar.