Dada una palabra, conviértala en un palíndromo con la mínima adición de letras [cerrado]

Question

Es difícil saber qué se pregunta aquí.Esta pregunta es ambigua, vaga, incompleta, demasiado amplia o retórica y no puede responderse razonablemente en su forma actual.Para obtener ayuda para aclarar esta pregunta y poder volver a abrirla, visita el centro de ayuda.

Cerrado hace 7 años.

Aquí hay una pregunta de entrevista bastante interesante:

Dada una palabra, añádale el menor número de letras para convertirla en un palíndromo.

Por ejemplo, si "hola" es la cadena dada, el resultado debería ser " hellolleh."Si se da "coco", el resultado debería ser " cococ."

Un enfoque que se me ocurre es agregar el reverso de la cadena al final de la cadena original y luego tratar de eliminar los caracteres adicionales del final.Sin embargo, no puedo entender cómo hacer esto de manera eficiente.¿Alguien tiene alguna idea?

Answer 1

Primero haga una función para probar la cadena de palíndromos, teniendo en cuenta que " a " y " aa " son palíndromos.Son palíndromos, ¿verdad???

Si la entrada es un palíndromo, devuélvala (se necesitan agregar 0 caracteres) Repita desde x [longitud] hasta x[1] comprobando si el subconjunto de la cadena x [i]..x [longitud] es un palíndromo, para encontrar el palíndromo más largo.

Tome la subcadena de la cadena de entrada antes del palíndromo más largo, revirtiéndola y agregándola al final debería hacer el palíndromo más corto mediante la adición.

coco = > c + oco = > c + oco + c

mmmeep = > mmmee + p = > mmmee + p + emmm

Answer 2

¡Bien!Aquí está mi segundo intento.

La idea es que queramos encontrar cuántos de los caracteres al final de la cadena se pueden reutilizar al agregar los caracteres adicionales para completar el palíndromo.Para hacer esto, usaremos una modificación del algoritmo de coincidencia de cadenas KMP.Usando KMP, buscamos su reverso en la cadena original.Una vez que lleguemos al final de la cadena, tendremos la mayor coincidencia posible entre el reverso de la cadena y la cadena original que ocurre al final de la cadena.Por ejemplo:

HELLO
    O

1010
 010

3202
 202

1001
1001

En este punto, KMP normalmente diría "sin coincidencia" a menos que la cadena original fuera un palíndromo.Sin embargo, dado que actualmente sabemos cuánto del reverso de la cadena coincidía, podemos simplemente averiguar cuántos caracteres aún faltan y luego agregarlos al final de la cadena.En el primer caso, nos falta LLEH.En el segundo caso, nos falta 1.En el tercero, nos falta 3.En el caso final, no nos falta nada, ya que la cadena inicial es un palíndromo.

El tiempo de ejecución de este algoritmo es el tiempo de ejecución de una búsqueda KMP estándar más el tiempo requerido para invertir la cadena:O (n) + O (n) = O (n).

Así que ahora para argumentar lo correcto.Esto requerirá un poco de esfuerzo.Considere la respuesta óptima:

   | original string | | extra characters |

Supongamos que estamos leyendo esto al revés desde el final, lo que significa que leeremos al menos el reverso de la cadena original.Parte de esta cuerda invertida se extiende hacia atrás en el cuerpo de la cuerda original.De hecho, para minimizar el número de caracteres agregados, este debe ser el mayor número posible de caracteres que termine de nuevo en la cadena misma.Podemos ver esto aquí:

   | original string | | extra characters |
           | overlap |

Ahora, ¿qué sucede en nuestro paso KMP?Bueno, cuando busque el reverso de la cadena dentro de sí mismo, KMP mantendrá una coincidencia lo más larga posible en todo momento, ya que funciona en toda la cadena.Esto significa que cuando el KMP llega al final de la cadena, la parte coincidente que mantiene será la coincidencia más larga posible, ya que KMP solo mueve el punto de partida de la coincidencia candidata hacia adelante en caso de falla.En consecuencia, tenemos esta superposición más larga posible, por lo que obtendremos el menor número posible de caracteres requeridos al final.

No estoy 100% seguro de que esto funcione, pero parece que funciona en todos los casos que puedo lanzar.La prueba de corrección parece razonable, pero es un poco ondulada a mano porque la prueba formal basada en KMP probablemente sería un poco complicada.

¡Espero que esto ayude!

Answer 3

Para responder, adoptaría este enfoque ingenuo:

1. ¿cuándo necesitamos 0 caracteres?cuando la cuerda es un palíndromo
2. ¿cuándo necesitamos 1 personaje?cuando, excepto la primera cadena de caracteres, es un palíndromo
3. ¿cuándo necesitamos 2 caracteres?cuando, excepto los 2 caracteres de inicio, la cadena es un palíndromo
4. etc, etc...

Entonces, un algoritmo podría ser

  for index from 1 to length
   if string.right(index) is palindrome
    return string + reverse(string.left(index))
   end
  next

editar

No soy mucho de Python, pero una implementación simple del pseudocódigo anterior podría ser

>>> def rev(s): return s[::-1]
... 
>>> def pal(s): return s==rev(s)
... 
>>> def mpal(s):
...  for i in range(0,len(s)):
...   if pal(s[i:]): return s+rev(s[:i])
... 
>>> mpal("cdefedcba")
'cdefedcbabcdefedc'
>>> pal(mpal("cdefedcba"))
True

Answer 4

Solución simple de tiempo lineal.

Llamemos a nuestra cadena S.

Sea f (X, P) la longitud del prefijo común más largo de X y P.Calcular f(S[0], rev(S)), f(S[1], rev(S)), ...donde S[ k] es el sufijo de S que comienza en la posición k.Obviamente, desea elegir el mínimo k de modo que k + f(S[k], rev(S)) = len (S).Eso significa que solo tienes que agregar k caracteres al final.Si k es 0, la picadura ya es un palíndromo.Si k = len (S), entonces necesita agregar todo el reverso.

Necesitamos calcular f (S[i], P) para todos los S[i] rápidamente.Esta es la parte complicada.Crea un árbol de sufijos de S.Recorra el árbol y actualice cada nodo con la longitud del prefijo común más largo con P.Los valores en las hojas corresponden a f (S [i], P).