Un k-palíndromo es una cadena que se transforma en un palíndromo al eliminar como máximo k caracteres de él. Dada una cadena S y un número entero K, ¿encuentra si S es un k-palíndromo o no? Restricciones: S tiene como máximo 20,000 caracteres y 0 <= k <= 30

Suraj explica la misma idea que mencioné en mi respuesta en CareerCup – Facebook Interview Question for Interns

La pregunta pregunta si podemos transformar la cadena S dada en su eliminación inversa en la mayoría de las letras K.

Podríamos modificar el algoritmo tradicional de Editar-Distancia, considerando solo las eliminaciones, y verificar si esta distancia de edición es <= K. Sin embargo, hay un problema. S puede tener una longitud = 20,000 y el algoritmo Editar-Distancia toma O (N ^ 2). Lo cual es muy lento.

(De aquí en adelante, supondré que está familiarizado con el algoritmo Editar-Distancia y su matriz DP)

Sin embargo, podemos aprovechar K. Solo estamos interesados ​​* si * logramos eliminar las letras K. Esto significa que cualquier posición a más de K posiciones de distancia de la diagonal principal es inútil porque su distancia de edición debe exceder esas K eliminaciones.

Como estamos comparando la cadena con su reverso, haremos como máximo K eliminaciones e inserciones K (para que sean iguales). Por lo tanto, debemos verificar si ModifiedEditDistance es <= 2 * K

Aquí está el código:

  int ModifiedEditDistance (const string & a, const string & b, int k) {
   int i, j, n = a.size ();
   // muestra por simplicidad.  deberíamos usar solo una ventana de tamaño 
   // 2 * k + 1 o dp [2] [MAX] y filas alternativas.  solo necesita la fila i-1
   int dp [MAX] [MAX];
   memset (dp, 0x3f, tamaño de dp);  // init a un valor> 1.000.000.000
   para (i = 0; i 
  Solo procesamos 2 * K + 1 columnas por fila.  Entonces este algoritmo funciona en O (N * K), que es lo suficientemente rápido. 
    

Se puede hacer O (n * k) complejidad de tiempo. Básicamente, necesitamos encontrar si la cadena S se puede convertir a su reversa dentro de 2 * k de inserción y eliminación.

Dejame explicarte con un ejemplo. Digamos que la cadena (S) es aabca. Entonces reverso (S ‘) es acbaa. Después de casi la eliminación de k, queremos que la cadena sea un palíndromo, es decir, se lea igual en dirección hacia atrás, es decir, hacia atrás. Podemos tratar esto como un problema de distancia de edición donde solo se permite la eliminación e inserción.

aabca -> (eliminar) abca -> (insertar) acbca -> (eliminar) acba -> (insertar) acbaa

Tenga en cuenta que, eliminar un carácter de la cadena S en realidad se traduce en dos operaciones aquí. Por lo tanto, tenemos que averiguar si S se puede convertir a S ‘con una eliminación de inserción de 2 * k.

Como solo se permite la eliminación de k, al comparar el carácter de S y S ‘, no necesitamos mirar más allá del carácter k (tanto hacia atrás como hacia adelante). Esto se puede hacer en O (n * k) complejidad de tiempo. La complejidad espacial es O (k).