string - non - longest increasing subsequence online

Buscando una cadena mínima que cumpla algunas condiciones

Question

Recientemente, me preguntaron el siguiente problema durante una entrevista.

Dada una cadena S, necesito encontrar otra cadena S2 tal que S2 sea una subsecuencia de S y también S sea una subsecuencia de S2 + inversa (S2). Aquí ''+'' significa concatenación. Necesito dar salida a la longitud mínima posible de S2 para un S. dado

Me dijeron que este es un problema de programación dinámica, pero no pude resolverlo. ¿Puede alguien ayudarme con este problema?

EDITAR-

¿Hay alguna manera de hacer esto en O (N ² ) o menos?

Answer 1

Cada personaje de S puede ser incluido en S2 o no. Con eso podemos construir una recursión que trata dos casos:

• El primer carácter de S se utiliza para cubrir,
• El primer carácter de S no se utiliza para cubrir,

y calcule el mínimo de estas dos cubiertas. Para implementar esto, es suficiente hacer un seguimiento de la cantidad de S que está cubierta con el S2 + reverso ya elegido (S2).

Hay optimizaciones en las que sabemos cuál es el resultado (cobertura encontrada, no puede tener cobertura), y no es necesario tomar el primer carácter para la cobertura si no cubre algo.

Implementación simple de python:

cache = {}

def S2(S, to_cover):
    if not to_cover:  # Covered
        return ''''
    if not S:         # Not covered
        return None
    if len(to_cover) > 2*len(S):  # Can''t cover
        return None
    key = (S, to_cover)
    if key not in cache:
        without_char = S2(S[1:], to_cover)     # Calculate with first character skipped
        cache[key] = without_char
        _f = to_cover[0] == S[0]
        _l = to_cover[-1] == S[0]
        if _f or _l:
            # Calculate with first character used
            with_char = S2(S[1:], to_cover[int(_f):len(to_cover)-int(_l)])
            if with_char is not None:
                with_char = S[0] + with_char  # Append char to result
                if without_char is None or len(with_char) <= len(without_char):
                    cache[key] = with_char
    return cache[key]

s = ''21211233123123213213131212122111312113221122132121221212321212112121321212121132''
c = S2(s, s)
print len(s), s
print len(c), c

Answer 2

Digamos que S2 es "manzana". Entonces podemos hacer esta suposición:

S2 + reverseS2 > = S > = S2
"appleelppa" > = S > = "manzana"

Así que la S dada será algo que incluye "manzana" a no más que "manzanaelppe". Podría ser "Appleel" o "Appleelpp".

String S ="locomotiffitomoc";
// as you see S2 string is "locomotif" but 
// we don''t know S2 yet, so it''s blank
String S2 = "";
for (int a=0; a<S.length(); a++) {
    try {
        int b = 0;
        while (S.charAt(a - b) == S.charAt(a + b + 1))
            b++;
        // if this for loop breaks that means that there is a character that doesn''t match the rule
        // if for loop doesn''t break but throws an exception we found it.
    } catch (Exception e) {
        // if StringOutOfBoundsException is thrown this means end of the string.
        // you can check this manually of course.
        S2 = S.substring(0,a+1);
        break;
    }
}
System.out.println(S2); // will print out "locomotif"

Enhorabuena, has encontrado el mínimo S2.

Answer 3

Hay 2 aspectos importantes en este problema.

1. Como necesitamos S como una subcadena de S2 + inversa (S2), S2 debería tener una longitud de al menos n / 2.
2. Después de la concatenación de S2 y reversa (S2), hay un patrón donde se repiten los alfabetos, como

Así que la solución es verificar desde el centro de S hasta el final de S para cualquier elemento consecutivo. Si encuentra uno, verifique los elementos en cada lado como se muestra.

Ahora, si puede alcanzar hasta el final de la cadena, entonces el número mínimo de elementos (resultado) es la distancia desde el inicio hasta el punto donde encuentra elementos consecutivos. En este ejemplo su C es 3.

Sabemos que esto puede no suceder siempre. es decir, es posible que no pueda encontrar elementos consecutivos en el centro. Digamos que los elementos consecutivos están después del centro, entonces podemos hacer la misma prueba.

Cuerda principal

Subcadena

Cuerda concatenada

Ahora llega la mayor duda. ¿Por qué consideramos sólo el lado izquierdo a partir del centro? La respuesta es simple, la cadena concatenada está hecha por S + reverse (S). Así que estamos seguros de que el último elemento en la subcadena viene consecutivo en la cadena concatenada. No hay forma de que cualquier repetición en la primera mitad de la cadena principal pueda dar un mejor resultado porque al menos deberíamos tener los n alfabetos en la cadena concatenada final

Ahora, la cuestión de la complejidad: la búsqueda de alfabetos consecutivos da un máximo de O (n). Ahora, la verificación de los elementos de cada lado puede dar una complejidad de O (n) en el peor de los casos. Es decir, máximas n / 2 comparaciones. Podemos fallar muchas veces haciendo la segunda verificación, por lo que tenemos una relación multiplicativa entre las complejidades, es decir, O (n * n).

Creo que esta es una solución correcta y no encontré ninguna laguna todavía.