Verificar renomeação consistente
A missão
Problema
Dois textos têm o mesmo formato se um puder ser transformado no outro renomeando caracteres. Uma renomeação precisa ser consistente nos dois sentidos: toda ocorrência de um caractere vira o mesmo substituto, e dois caracteres diferentes não podem compartilhar um substituto. Decida se essa renomeação existe.
Exemplos
Input: a = "egg", b = "add"
Output: True
Por quê: e vira a e g vira d, de forma consistente
Input: a = "foo", b = "bar"
Output: False
Por quê: o teria de virar a e r ao mesmo tempo
Input: a = "ab", b = "aa"
Output: False
Por quê: edge case: dois caracteres não podem convergir para o mesmo substituto
Dicas
0 / 3
Os caracteres na mesma posição dos dois textos sempre formam um par, então a pergunta inteira é se esses pares em algum momento se contradizem.
Registrar os pares conforme você avança transforma a verificação em uma busca. Um mapa sozinho não basta, porque só detecta contradições em um sentido.
Mantenha dois mapas, um de cada lado para o outro. Em cada posição, se algum dos mapas já tiver uma entrada para o seu caractere, ela precisa concordar com o par atual; caso contrário, registre a nova entrada. Uma discordância em qualquer sentido encerra a verificação na hora.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(n)
Solução
Percorrer os dois textos juntos forma pares de caracteres posição por posição, e uma renomeação válida significa que nenhum par contradiz um anterior. São necessários dois mapas, e não um: o mapa de ida detecta um caractere sendo renomeado de dois jeitos diferentes, e o mapa de volta detecta dois caracteres convergindo para o mesmo substituto. Registrar na primeira vez e comparar dali em diante faz as duas verificações em uma única passada. O tempo é O(n) em média, e o espaço é O(k) para os 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")) # -> FalseTravou na ideia, e não no código? O básico de tabelas hash explica isso.