Utilice hábilmente un algoritmo codicioso para calcular el palíndromo de cuerdas
Dada una cadena que contiene letras mayúsculas y minúsculas, encuentre la cadena palíndromo más larga construida a partir de estas letras.
Durante la construcción, tenga en cuenta la distinción entre mayúsculas y minúsculas. Por ejemplo, "Aa" no puede tratarse como una cadena palíndromo.
Nota:
Supongamos que la longitud de la cadena no excederá 1010.
Ejemplo 1:
Entrada:
"abccccdd"
Salida:
7
Explicación:
La cadena palíndromo más larga que podemos construir es "dccaccd", su longitud es 7.
Dada una cadena que contiene letras mayúsculas y minúsculas, encuentre la cadena palíndromo más larga construida a partir de estas letras.
¡Tenga en cuenta! ! !
El significado de la pregunta es: Usa todas las letras de esta cadena para construir la cadena palíndromo más larga. ¡Es una construcción! ¡Es posible cambiar el orden en que aparecen las letras! La posición de la letra se puede mover arbitrariamente. En lugar de encontrar la cadena palíndromo más larga sin cambiar el orden.
El autor fue descuidado al principio y no entendió el significado de la pregunta, por lo que inmediatamente comenzó a resolver la pregunta y sufrió una gran pérdida (cubrirse la cara.
Ahora expliquemos, ¿Qué es un palíndromo?
Un palíndromo es una cadena que se lee igual al derecho y al revés
Veamos dos ejemplos diferentes de palíndromos:
Solo mira. en AB|BA Letras, encontramos que AB y BA son simétricos según la línea vertical central |, la longitud de esta cadena palíndromo es 4 y el número de apariciones de cada letra es un número par
<. p>Encontramos que AB y BA son simétricos según las letras. C es simétrica. La longitud de esta cadena palíndromo es 5. Excepto por la letra C en el centro de la simetría, que aparece solo una vez, las letras en ambos lados. del centro aparece un número par.Por lo que podemos concluir que si queremos construir una cadena palíndromo, además la letra en el centro de la cadena palíndromo aparece solo una vez (si la hay). es una letra central), las letras a ambos lados del centro también deben aparecer simétricamente, es decir, un número par de veces
Construcción resuelta El punto clave de la cadena palíndromo es que hay. otra característica especial en la pregunta: solo aparecen letras mayúsculas y minúsculas
Si está familiarizado con la codificación Unicode de las letras inglesas, puede saber que la codificación Unicode de la letra A es 65 (. decimal), la codificación Unicode de la letra Z es 90 (decimal), la codificación Unicode de la letra a es 97 (decimal) y la codificación Unicode de la letra z es 122 (decimal)
Puede encontrar que las codificaciones Unicode son continuas (91 a 96 en el medio no son importantes), es decir, ordenadas, por lo que puede usar una matriz para almacenarlas. El valor de cada elemento de la matriz es el número de veces que se escribe cada letra. aparece
Esto. En este caso, usar una matriz para almacenar será más eficaz que usar una tabla hash (Mapa) para almacenar, incluso si no necesitamos usar la codificación Unicode 91 a 97 <. /p>
Además, en el mundo de JavaScript, puedes usar la API String.prototype.charCodeAt() para obtener la unidad de codificación Unicode.
Entonces, podemos contar el número de apariciones de cada letra. así: