Isomorphic Strings

Q: Por que você precisa de dois mapas hash para strings isomórficas?

Um mapeamento de s para t detecta um caractere de s renomeado de duas maneiras. Ele não consegue detectar dois caracteres de s renomeados para o mesmo caractere, como em ab e aa . O mapeamento de t de volta para s detecta esse caso.

Q: O isomorfismo é simétrico?

Sim. Uma renomeação um a um pode ser desfeita, então, se s for renomeado para t , inverter cada nome transforma t de volta em s . isIsomorphic(s, t) e isIsomorphic(t, s) sempre concordam.

FácilHashing

+10

Duas strings são isomórficas quando você pode renomear os caracteres da primeira para obter a segunda. Todas as ocorrências de um caractere recebem o mesmo novo nome, dois caracteres diferentes nunca recebem o mesmo nome, e um caractere pode manter o próprio nome. Para duas strings s e t do mesmo comprimento, retorne true quando forem isomórficas e false quando não forem.

Função

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

sstring: a string a ser renomeada, letras e dígitos
tstring: uma string a ser alcançada, com o mesmo comprimento que s
Retornaboolean: verdadeiro se uma renomeação bijetiva dos caracteres de s resulta em t

Restrições

1 ≤ s.length ≤ 2 × 10⁴
t.length == s.length
s e t contêm apenas letras do alfabeto inglês e dígitos. Letras maiúsculas e minúsculas são caracteres diferentes.

Exemplos

Entrada: s = "noon"t = "deed"
Saída: true
Explicação: Renomeie n para d e o para e. Todas as posições estão de acordo com essa renomeação, e as duas letras recebem nomes diferentes.

Entrada: s = "moon"t = "deed"
Saída: false
Explicação: Da esquerda para a direita, m se torna d e o se torna e, e então n também teria que se tornar d. Duas letras diferentes não podem compartilhar um nome, então a resposta é false.

Entrada: s = "r2d2"t = "c3p3"
Saída: true
Explicação: r se torna c, 2 se torna 3 e d se torna p. Dígitos também são caracteres, e ambos os 2 se tornam 3.

Para ir além

Dada uma lista de palavras, você consegue agrupar as que são isomorfas entre si sem comparar todos os pares de palavras?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Uma renomeação deve funcionar nos dois sentidos: cada caractere de s se transforma em um caractere de t, e cada caractere de t vem de um caractere de s. Dois mapeamentos, um para cada direção, verificam ambos em uma única passagem.

Compare cada par de posições

Correta, mas não termina nos maiores testes

Intuição

Uma renomeação mantém iguais os caracteres iguais e diferentes os caracteres diferentes. Portanto, para cada par de posições i e j, s[i] == s[j] deve produzir a mesma resposta que t[i] == t[j]. Isso também é suficiente: se todos os pares concordarem, renomear cada caractere de s para o caractere de t em suas posições será bem definido e nunca atribuirá o mesmo nome a dois caracteres. Em moon e deed, as posições 0 e 3 contêm letras diferentes em s, mas duas vezes d em t, então a resposta é false.

Há cerca de n²/2 pares: 2 × 10^8 comparações quando n = 2 × 10^4, caso nenhum par interrompa o loop antes do fim.

Algoritmo

Percorra todos os índices i e, para cada um, todos os índices posteriores j.
Verifique se s[i] é igual a s[j] e se t[i] é igual a t[j].
Se as duas respostas forem diferentes, retorne false.
Após o último par, retorne 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

Duas maps, uma para cada direção

Intuição

Construa o mapeamento de renomeação enquanto lê. sToT registra em que cada caractere de s se tornou, e tToS registra de onde veio cada caractere de t. Na posição i, com a = s[i] e b = t[i], ou ambos são novos e você os associa, ou eles já devem apontar um para o outro.

Um mapa não basta. Usando apenas sToT, moon e deed são aceitos, porque nenhuma letra de s é renomeada de duas maneiras. O problema é que m e n se tornam d, e, na posição 3, tToS já indica que d veio de m.

Cada posição custa algumas operações de mapa, então o tempo é O(n). O código de cada caractere é menor que 128, então cada mapa pode ser um array com 128 entradas: espaço O(1). As versões em R e Swift primeiro copiam as strings para arrays de códigos, o que leva O(n).

Algoritmo

Crie dois mapas vazios, sToT e tToS.
Para cada índice i, defina a = s[i] e b = t[i].
Se a não estiver em sToT e b não estiver em tToS, mapeie a para b e b para a.
Caso contrário, se sToT[a] não for b ou tToS[b] não for a, retorne false.
Após o último índice, retorne 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

Armadilhas e casos extremos

Mantém um único mapeamento de s para t. Ele aceita moon e deed, e ab e aa.
Compara quantas vezes cada caractere aparece. abcabc e xyzxzy usam ambos três caracteres duas vezes cada, mas o segundo b fica sobre z, enquanto o primeiro ficou sobre y.
Trata maiúsculas e minúsculas como iguais. aA contém dois caracteres diferentes, então não pode se tornar bb.
Dimensiona os mapas do array apenas para a a z. Letras maiúsculas e dígitos ficam fora desse intervalo; use o código completo do caractere como índice, com 128 posições.

Perguntas frequentes4

Qual é a complexidade de tempo de Strings Isomórficas?

A solução com dois mapas lê cada posição uma vez, então é executada em O(n) de tempo. Os mapas contêm no máximo uma entrada por caractere possível: 62 letras e dígitos; portanto, o espaço extra é O(1). Comparar cada par de posições leva O(n²).

Por que você precisa de dois mapas hash para strings isomórficas?

Um mapeamento de s para t detecta um caractere de s renomeado de duas maneiras. Ele não consegue detectar dois caracteres de s renomeados para o mesmo caractere, como em ab e aa. O mapeamento de t de volta para s detecta esse caso.

O isomorfismo é simétrico?

Sim. Uma renomeação um a um pode ser desfeita, então, se s for renomeado para t, inverter cada nome transforma t de volta em s. isIsomorphic(s, t) e isIsomorphic(t, s) sempre concordam.

De que outra forma você pode verificar se duas strings são isomórficas?

Substitua cada caractere pela posição em que ele aparece pela primeira vez e compare os resultados. noon e deed se tornam 0 1 1 0, enquanto moon se torna 0 1 1 3. Isso também leva O(n) de tempo, com O(n) de memória para os dois padrões.

def isIsomorphic(s, t):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

s = "noon"
t = "deed"

Saída Esperada

true