cómo convertir una cadena en un palíndromo con un número mínimo de operaciones?

Question

Aquí está el problem estados para convertir una cadena en un palíndromo con un número mínimo de operaciones. Sé que es similar a la Levenshtein distance pero no puedo resolverlo sin embargo

Por ejemplo, para la entrada mohammadsajjadhossain, la salida es 8.

Answer 1

Realiza la distancia Levenshtein en la cuerda y su reverso. La solución será el mínimo de las operaciones en la diagonal de la matriz DP que va de abajo a la izquierda a arriba a la derecha, así como de cada entrada justo arriba y justo debajo de la diagonal.

Esto funciona porque las entradas a lo largo de la diagonal representan las ediciones mínimas requeridas para hacer que el primer y último caracteres Ni de la cadena sean iguales y las entradas justo arriba y justo debajo representan el mínimo para las cadenas que terminan con longitud impar donde el personaje del medio (sobrante) no coincide con nada.

Answer 2

Solo necesita calcular un número limitado de distancias de Levenshtein, una para cada posible punto de pivote del palíndromo. Un punto de pivote puede ser una letra o puede estar entre dos letras, por lo que una cadena de longitud n tiene 2n-1 puntos de pivote. Para cada punto de giro, se calcula la distancia Levenshtein de los caracteres antes del punto de pivote y el reverso de los caracteres después de que:

(m)ohammadsajjadhossain: Levensthein("", "niassohdajjasdammaho")
m ohammadsajjadhossain: Levensthein("m", "niassohdajjasdammaho")
m(o)hammadsajjadhossain: Levensthein("m", "niassohdajjasdammah")
mo hammadsajjadhossain: Levensthein("mo", "niassohdajjasdammah")
mo(h)ammadsajjadhossain: Levensthein("mo", "niassohdajjasdamma")
moh ammadsajjadhossain: Levensthein("moh", "niassohdajjasdamma")
etc.

Ahora solo tome el mínimo de estas distancias. Si la velocidad es importante, puede optimizar muchas de estas llamadas.