LeetCode: Generate Parenthesis.

En este post te voy a explicar la solución del problema Generate Parenthesis de la plataforma Leetcode.

Primeros pasos.

Este problema, Generate Parenthesis, necesita de una estrategia. El problema consiste en generar el mayor número posible de combinaciones de paréntesis válidas. El número de paréntesis que abren y cierran deben de coincidir en número y posición. Un approach de fuerza bruta no vale, necesitas validar cada resultado.

Puedes tener una estrategia para reducir el número de iteraciones, como, siempre, empezar con «(«. Cualquier lista que empiece con el otro paréntesis es incorrecta.  También el número de paréntesis de apertura y cierre debe ser igual. Un número distinto en un listado completo es erróneo. Adicional, todos los listados deben de finalizar con el paréntesis de cierre.

Estos consejos pueden reducirte en mucho los resultados, pero, vas a tener que revisar cada solución parcial por su validez. Una solución parcial es aquella que tiene menos elementos que n*2. Al descartar soluciones parciales, le quitas al algoritmo la posibilidad de iterar hasta el final una solución que no va a ninguna parte.

Solución.

Gustavo Sánchez

Soy especialista en escribir software de calidad. Mediante el uso de marcos de trabajo, técnicas y automatización de procesos he podido reducir los costes operativos de los sistemas de la empresa. Sistemas confiables y adaptables producen clientes felices.