Isomorphic Strings

Q: ¿Por qué necesitas dos mapas hash para las cadenas isomorfas?

Un mapa de s a t detecta que un carácter de s se renombre de dos maneras. No puede detectar que dos caracteres de s se renombren al mismo carácter, como en ab y aa . El mapa de t a s detecta ese caso.

FácilHashing

+10

Dos cadenas son isomorfas cuando puedes cambiar el nombre de los caracteres de la primera para obtener la segunda. Cada aparición de un carácter recibe el mismo nombre nuevo, dos caracteres diferentes nunca reciben el mismo nombre y un carácter puede conservar el suyo. Para dos cadenas s y t de la misma longitud, devuelve true cuando sean isomorfas y false cuando no lo sean.

Función

isIsomorphic(s: string, t: string) → boolean

sstring: la cadena que se va a renombrar, letras y dígitos
tstring: la cadena a la que llegar, de la misma longitud que s
Devuelveboolean: verdadero si un renombramiento uno a uno de los caracteres de s da como resultado t

Restricciones

1 ≤ s.length ≤ 2 × 10⁴
t.length == s.length
s y t contienen solo letras y dígitos en inglés. Las mayúsculas y las minúsculas son caracteres distintos.

Ejemplos

Entrada: s = "noon"t = "deed"
Salida: true
Explicación: Cambia el nombre de n por d y el de o por e. Todas las posiciones concuerdan con ese cambio de nombre, y las dos letras reciben nombres diferentes.

Entrada: s = "moon"t = "deed"
Salida: false
Explicación: De izquierda a derecha, m se convierte en d y o se convierte en e, y después n también tendría que convertirse en d. Dos letras diferentes no pueden compartir un nombre, así que la respuesta es false.

Entrada: s = "r2d2"t = "c3p3"
Salida: true
Explicación: r se convierte en c, 2 se convierte en 3 y d se convierte en p. Los dígitos también son caracteres, y ambos 2 se convierten en 3.

Para ir más allá

Dada una lista de palabras, ¿puedes agrupar las que son isomorfas entre sí sin comparar cada par de palabras?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Un cambio de nombre debe funcionar en ambas direcciones: cada carácter de s se convierte en un carácter de t, y cada carácter de t proviene de un carácter de s. Dos mapas, uno por dirección, comprueban ambas en una sola pasada.

Compara cada par de posiciones

Correcto, pero no termina con las pruebas más grandes

Intuición

Un cambio de nombre mantiene iguales los caracteres iguales y diferentes los caracteres diferentes. Así que, para cada par de posiciones i y j, s[i] == s[j] debe dar la misma respuesta que t[i] == t[j]. Eso también es suficiente: si todos los pares coinciden, cambiar el nombre de cada carácter de s por el carácter de t en sus posiciones está bien definido y nunca da el mismo nombre a dos caracteres. En moon y deed, las posiciones 0 y 3 contienen letras diferentes en s, pero dos veces d en t, así que la respuesta es false.

Hay alrededor de n²/2 pares: 2 × 10^8 comparaciones con n = 2 × 10^4 cuando ningún par detiene el bucle antes de tiempo.

Algoritmo

Recorre todos los índices i y, para cada uno, todos los índices posteriores j.
Determina si s[i] es igual a s[j] y si t[i] es igual a t[j].
Si las dos respuestas son diferentes, devuelve false.
Después del último par, devuelve true.

def isIsomorphic(s, t):
    n = len(s)
    for i in range(n):
        for j in range(i + 1, n):
            # Two positions must hold equal characters in s exactly when they do in t
            if (s[i] == s[j]) != (t[i] == t[j]):
                return False
    return True

Dos mapas, uno por dirección

Intuición

Construye el renombrado mientras lees. sToT registra en qué se convirtió cada carácter de s, y tToS registra de dónde provino cada carácter de t. En la posición i, con a = s[i] y b = t[i], o bien ambos son nuevos y los vinculas, o bien ya deben apuntarse mutuamente.

Un mapa no es suficiente. Con solo sToT, moon y deed pasan, porque ninguna letra de s se renombra de dos maneras. El problema es que tanto m como n se convierten en d, y en la posición 3 tToS ya indica que d provino de m.

Cada posición requiere unas pocas operaciones de mapa, así que el tiempo es O(n). El código de cada carácter es menor que 128, por lo que cada mapa puede ser un arreglo de 128 elementos: espacio O(1). Las versiones de R y Swift primero copian las cadenas en arreglos de códigos, lo que toma O(n).

Algoritmo

Crea dos mapas vacíos, sToT y tToS.
Para cada índice i, sean a = s[i] y b = t[i].
Si a no está en sToT y b no está en tToS, asigna a a b y b a a.
De lo contrario, si sToT[a] no es b o tToS[b] no es a, devuelve false.
Después del último índice, devuelve true.

def isIsomorphic(s, t):
    s_to_t = {}  # the character of t that each character of s became
    t_to_s = {}  # the character of s that each character of t came from
    for a, b in zip(s, t):
        if a not in s_to_t and b not in t_to_s:
            s_to_t[a] = b
            t_to_s[b] = a
        elif s_to_t.get(a) != b or t_to_s.get(b) != a:
            return False  # a already has another target, or b another source
    return True

Errores comunes y casos límite

Mantener un mapa de s a t. Acepta moon y deed, y ab y aa.
Comparar cuántas veces aparece cada carácter. abcabc y xyzxzy usan ambos tres caracteres dos veces cada uno, pero la segunda b queda sobre la z, donde la primera quedaba sobre la y.
Tratar las mayúsculas y las minúsculas como iguales. aA contiene dos caracteres diferentes, así que no puede convertirse en bb.
Dimensionar los arreglos de mapas para que solo abarquen de a a z. Las letras mayúsculas y los dígitos quedan fuera de ese rango; usa como índice el código de carácter completo, con 128 entradas.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de las cadenas isomorfas?

La solución con dos mapas lee cada posición una vez, así que se ejecuta en tiempo O(n). Los mapas contienen como máximo una entrada por cada carácter posible, 62 letras y dígitos, así que el espacio adicional es O(1). Comparar cada par de posiciones lleva O(n²).

¿Por qué necesitas dos mapas hash para las cadenas isomorfas?

Un mapa de s a t detecta que un carácter de s se renombre de dos maneras. No puede detectar que dos caracteres de s se renombren al mismo carácter, como en ab y aa. El mapa de t a s detecta ese caso.

¿Es simétrico el isomorfismo?

Sí. Un cambio de nombre uno a uno se puede deshacer, así que, si s se renombra como t, invertir todos los nombres convierte t de nuevo en s. isIsomorphic(s, t) y isIsomorphic(t, s) siempre coinciden.

¿De qué otra manera puedes comprobar si dos cadenas son isomorfas?

Reemplaza cada carácter por la posición en la que aparece por primera vez y compara los resultados. noon y deed se convierten ambos en 0 1 1 0, mientras que moon se convierte en 0 1 1 3. También tiene un tiempo de O(n) y usa O(n) de memoria para los dos patrones.

def isIsomorphic(s, t):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumentos

s = "noon"
t = "deed"

Salida Esperada

true