El enfoque ingenuo de encontrar todos los anagramas posibles y determinar si alguno de ellos es un palíndromo tiene una complejidad exponencial.
Sugiero el siguiente algoritmo que tiene complejidad polinómica.
Algoritmo:
1. Tome la cadena de entrada
2. ¿La longitud de la cuerda es pareja?
Goto 3 más Goto 4.
3. Encuentra la aparición de cada carácter en cadena,
Si la aparición de cada personaje es par
Salida sí. ir a 5
más
Salida NO. ir a 5
4. Encuentra la aparición de cada personaje
Si la aparición de cada carácter es par, y la aparición de exactamente un carácter es impar.
Salida sí. ir a 5
más
Salida No. goto 5
5. Parar
Ejemplo:
Cadena: aacddc
longitud par, la aparición de cada carácter es 2 (par) ,, Resultado Sí
Cadena: aaacddc
Longitud impar, la aparición de cada carácter es 2 (par) excepto ‘a’ que es 3 … Resultado Si.
Cadena: aaacccdde
Longitud impar, ocurrencia de 3 caracteres impares (a, c, d). Resultado, NO
- ¿Cuáles son algunos ejemplos de problemas que son: (1) NP pero no NP-Complete; (2) NP-Completo; (3) NP-Hard pero no NP-Complete?
- ¿Cómo puedo aprender los algoritmos de resolución de problemas solo?
- ¿Hay un árbol que pueda agregar y eliminar nodos más rápido que AVL?
- ¿Qué tan importante es el DS y Algo?
- ¿Cuál fue el algoritmo utilizado por AlphaGo para ganar el juego de Go contra el campeón europeo de Go humano?
Prueba:
Cadena de longitud uniforme:
Para que una cadena sea palíndromo, para cada carácter en el lado izquierdo del punto medio de la cadena, debe haber el mismo carácter en el lado derecho del punto medio.
Cadena de longitud impar:
Para que una cadena sea palíndromo, para cada carácter en el lado izquierdo del punto medio de la cadena, debe haber el mismo carácter en el lado derecho del punto medio. de personajes lo flanquean a ambos lados.
