Consideremos la estructura general de cualquier paréntesis válido. Cualquier estructura necesariamente tendrá un prefijo más corto que sea un paréntesis válido (que puede ser el paréntesis completo). Aprovecharemos este hecho para calcular todas las paréntesis válidas de manera eficiente.
Digamos que la función que queremos implementar es GenerateAllParenthesizations. También implementaremos otra función, que llamaremos GeneratePrefixFreeParenthesization. Aquí están las especificaciones para ambas funciones:
GenerateAllParenthesizations tomará los números de símbolos dados y devolverá todos los paréntesis válidos de las cantidades de símbolos especificadas.
- ¿Hay algún buen sitio para aprender algoritmos / conceptos de programación todos los días (similar a la pregunta SAT del día)?
- Cómo reducir los componentes fuertemente conectados en nodos únicos de manera eficiente si estoy usando una representación de lista de adyacencia
- ¿Qué estructuras de datos admiten la inserción, eliminación y selección de un elemento aleatorio con un límite de complejidad de tiempo O (1) que permite duplicados?
- ¿Cuántos niveles habrá en un árbol completamente binario si tiene n número de nodos?
- Si la compresión sin pérdida es completamente reversible, ¿por qué no omitimos un paso y solo usamos los archivos en su estado comprimido?
GeneratePrefixFreeParenthesization tomará el número dado de símbolos y devolverá todos los paréntesis válidos de las cantidades especificadas de símbolos que no tienen un prefijo más corto que sea válido.
Consideremos esta segunda función primero. ¿Qué sabemos sobre tal paréntesis? Bueno, si hay corchetes, el primer carácter debe ser un corchete de apertura y el último carácter debe ser un corchete de cierre. Si este no fuera el caso, entonces los corchetes se encontrarán inválidamente dentro de otros corchetes o habrá un prefijo más corto que es un paréntesis válido. Podemos derivar una regla similar si no hay corchetes, pero hay corchetes. Si solo hay paréntesis, el primer y el último carácter deben ser un paréntesis de apertura y un paréntesis de cierre, respectivamente. Una vez que se establecen esos caracteres, podemos generar arbitrariamente paréntesis con los símbolos restantes.
Ahora, volvamos a la primera función. Sabemos que cada paréntesis válido debe tener un prefijo más corto. Por lo tanto, aplicaremos la fuerza bruta sobre todas las [matemáticas] (n_1 + 1) (n_2 + 1) (n_3 + 1) -1 [/ matemáticas] posibles recuentos de paréntesis que debe tener el prefijo más corto y usaremos GeneratePrefixFreeParenthesization para obtener todos esos prefijos Mientras tanto, podemos generar paréntesis válidos arbitrarios con los símbolos restantes, por lo que llamamos recursivamente GenerateAllParenthesizations con los recuentos restantes.
Esto elimina los pasos recursivos. La última parte es averiguar el caso base de GenerateAllParenthesizations – si no hay símbolos, entonces tenemos una cadena vacía.
Tendremos que memorizar los resultados de las llamadas anteriores para la eficiencia.
