Comprobar un renombrado consistente
La misión
Problema
Dos textos tienen la misma forma si uno se puede convertir en el otro renombrando caracteres. Un renombrado debe ser consistente en ambas direcciones: cada aparición de un carácter se transforma en el mismo reemplazo, y dos caracteres distintos no pueden compartir un reemplazo. Decide si existe un renombrado así.
Ejemplos
Input: a = "egg", b = "add"
Output: True
Por qué: e se convierte en a y g en d, de forma consistente
Input: a = "foo", b = "bar"
Output: False
Por qué: o tendría que convertirse en a y en r a la vez
Input: a = "ab", b = "aa"
Output: False
Por qué: caso límite: dos caracteres no pueden colapsar en el mismo reemplazo
Pistas
0 / 3
Los caracteres en la misma posición de los dos textos siempre van emparejados, así que toda la pregunta es si esos emparejamientos se contradicen alguna vez.
Registrar los emparejamientos sobre la marcha convierte la comprobación en una búsqueda. Un solo mapa no alcanza, porque solo detecta contradicciones en una dirección.
Mantén dos mapas, uno de cada lado hacia el otro. En cada posición, si alguno de los mapas ya tiene una entrada para su carácter, debe coincidir con el compañero actual; si no, registra la entrada nueva. Un desacuerdo en cualquiera de las dos direcciones termina la comprobación de inmediato.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(n)
Solución
Recorrer ambos textos a la vez empareja los caracteres posición por posición, y un renombrado válido significa que ningún par contradice nunca a uno anterior. Hacen falta dos mapas, no uno: el mapa de ida detecta un carácter renombrado de dos formas distintas, y el de vuelta detecta dos caracteres que colapsan en el mismo reemplazo. Registrar en la primera aparición y comparar a partir de ahí hace ambas comprobaciones en una sola pasada. El tiempo es O(n) en promedio, y el espacio es O(k) para los caracteres distintos.
def has_consistent_renaming(a, b):
if len(a) != len(b):
return False
forward, backward = {}, {} # a -> b and b -> a pairings seen so far
for x, y in zip(a, b):
# setdefault records a new pairing and returns the one already stored
if forward.setdefault(x, y) != y or backward.setdefault(y, x) != x:
return False
return True
print(has_consistent_renaming("egg", "add")) # -> True
print(has_consistent_renaming("foo", "bar")) # -> False
print(has_consistent_renaming("ab", "aa")) # -> False¿Lo que te frena es la idea y no el código? Fundamentos de la tabla hash lo explica.