Demostrar si los ciclos son suficientes para evitar la transformación de cadenas

Question

Pregunta de la entrevista.

Demostrar que si todos los caracteres de la transformación de la cadena A a la cadena B están en algunos ciclos entonces no se puede realizar dicha transformación y se necesitaría un carácter adicional por ciclo.

La anterior fue la última pregunta de la entrevista, pero esto es lo que sucedió:

Se le dan dos cadenas A y B. Tiene que devolver True si puede transformar la cadena A en la cadena B de un carácter a la vez y sólo puede utilizar los caracteres de la cadena A y B. Por ejemplo foo traducido a baa significa que f -> b , o -> a . No se pueden utilizar caracteres adicionales.

Otro ejemplo en el que se devolverá True : A = ghijk , B = hkjki

A = ghijk

Transformation: j -> h gives ghihk 

Transformation: i -> j gives ghjhk

Transformation: k -> i gives ghjhi

Transformation: h -> k gives gkjki

Transformation: g -> h gives hkjki = B

Un ejemplo en el que se devuelve False no se puede convertir abc a bca . No se puede convertir abc a bac también. Esto se debe a que abc -> bbc utilizando a->b transformación. Entonces b traducido a c daría ccc y no podrás conseguir bca .

El siguiente es el algoritmo que se nos ocurrió: Si ambas cadenas son iguales devolví True es decir abc puede convertirse en abc .

Si existen ciclos en los que todos los vértices forman parte de al menos un ciclo, entonces devuelve False, si no, devuelve True. Por ejemplo abc no se puede convertir en bca porque a mapas a b b mapas a a por lo tanto, un ciclo y a mapas a a que es un bucle propio otro ciclo. foo se puede asignar a baa porque no hay ningún ciclo.

ghijk se puede asignar a hkjki donde g -> h -> k -> i -> j ->k . Sólo hay un ciclo de k a i a j a k pero los otros caracteres g y h no forman parte de un ciclo.

Tenga en cuenta que la conversión de abc a bca se puede hacer teniendo un carácter más, es decir abc -> xbc -> xba -> xca -> bca donde tienes la transformación añadida a -> x -> b

Se le pidió que demostrara: Demostrar si existen ciclos en los que todos los vértices forman parte de al menos un ciclo, entonces devolver Falso, si no devolver Verdadero. Demostrar si se necesita un carácter adicional por ciclo si devuelve False.

Answer 1

Si tienes aunque sea un ciclo $l_1 \to l_2 \to \ldots \to l_k \to l_1$ Entonces, como no veo la opción de transformar dos letras a la vez, inevitablemente una de las letras [en el bucle/ciclo] se transformará primero . W.l.o.g. asume que esto es $l_1$ . Entonces, en el momento en que estés listo para transformar $l_2$ no puedes distinguir entre el original $l_2$ y transformado $l_1$ .

Añadir un carácter al bucle ayuda, pero sólo si no forma parte de alguna otra transformación, es decir, si existe $l_1 \to l_2$ No se puede tener una regla $l_3 \to l_1 \to l_4$ .

Digamos que tienes un bucle $l_1 \to l_2 \to \ldots \to l_k \to l_1$ y a continuación se añade la nueva regla $l_1 \to x \to l_2$ . Y aplicar $l_1 \to x$ primero, y luego todas las reglas del bucle desde el final hasta el principio. $l_k \to l_1$ entonces $l_{k-1} \to l_k$ etc. entonces $l_2 \to l_3$ y finalmente $x \to l_2$ .