Isomorphic Strings

Q: Perché ti servono due mappe hash per le stringhe isomorfe?

Una mappa da s a t rileva un carattere di s rinominato in due modi. Non può rilevare due caratteri di s rinominati nello stesso carattere, come in ab e aa . La mappa da t a s rileva quel caso.

Q: L'isomorfismo è simmetrico?

Sì. Una rinomina uno a uno può essere annullata, quindi se s viene rinominato in t , invertendo ogni nome si riporta t a s . isIsomorphic(s, t) e isIsomorphic(t, s) concordano sempre.

FacileHashing

+10

Due stringhe sono isomorfe quando puoi rinominare i caratteri della prima per ottenere la seconda. Ogni occorrenza di un carattere riceve lo stesso nuovo nome, due caratteri diversi non ricevono mai lo stesso nome e un carattere può mantenere il proprio. Per due stringhe s e t della stessa lunghezza, restituisci true quando sono isomorfe e false quando non lo sono.

Funzione

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

sstring: la stringa da rinominare, lettere e cifre
tstring: la stringa da raggiungere, della stessa lunghezza di s
Restituisceboolean: true se una ridenominazione uno a uno dei caratteri di s dà t

Vincoli

1 ≤ s.length ≤ 2 × 10⁴
t.length == s.length
s e t contengono solo lettere inglesi e cifre. Le lettere maiuscole e minuscole sono caratteri diversi.

Esempi

Input: s = "noon"t = "deed"
Output: true
Spiegazione: Rinomina n in d e o in e. Ogni posizione è coerente con questa rinomina e le due lettere ricevono nomi diversi.

Input: s = "moon"t = "deed"
Output: false
Spiegazione: Da sinistra a destra, m diventa d e o diventa e, e poi anche n dovrebbe diventare d. Due lettere diverse non possono condividere lo stesso nome, quindi la risposta è false.

Input: s = "r2d2"t = "c3p3"
Output: true
Spiegazione: r diventa c, 2 diventa 3 e d diventa p. Anche le cifre sono caratteri, ed entrambe le 2 diventano 3.

Per approfondire

Data una lista di parole, riesci a raggruppare quelle che sono isomorfe tra loro senza confrontare ogni coppia di parole?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Una rinominazione deve funzionare in entrambe le direzioni: ogni carattere di s diventa un carattere di t e ogni carattere di t proviene da un carattere di s. Due mappe, una per direzione, verificano entrambe le condizioni in un unico passaggio.

Confronta ogni coppia di posizioni

Corretto, ma non termina sui test più grandi

Intuizione

Una rinominazione mantiene uguali i caratteri uguali e diversi i caratteri diversi. Quindi, per ogni coppia di posizioni i e j, s[i] == s[j] deve dare la stessa risposta di t[i] == t[j]. Questo è anche sufficiente: se ogni coppia corrisponde, rinominare ogni carattere di s con il carattere di t nelle stesse posizioni è ben definito e non assegna mai lo stesso nome a due caratteri. In moon e deed, le posizioni 0 e 3 contengono lettere diverse in s ma due d in t, quindi la risposta è false.

Ci sono circa n²/2 coppie: 2 × 10^8 confronti con n = 2 × 10^4 se nessuna coppia interrompe il ciclo in anticipo.

Algoritmo

Esegui un ciclo su ogni indice i e, per ciascuno, su ogni indice successivo j.
Verifica se s[i] è uguale a s[j] e se t[i] è uguale a t[j].
Se le due risposte sono diverse, restituisci false.
Dopo l’ultima coppia, restituisci 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

Due mappe, una per direzione

Intuizione

Costruisci la mappatura dei rinominamenti man mano che leggi. sToT registra in cosa è diventato ogni carattere di s, mentre tToS registra da dove proviene ogni carattere di t. Alla posizione i, con a = s[i] e b = t[i], o sono entrambi nuovi e li colleghi, oppure devono già puntarsi a vicenda.

Una sola mappa non basta. Usando solo sToT, moon e deed superano il controllo, perché nessuna lettera di s viene rinominata in due modi diversi. Il problema è che m e n diventano entrambi d, e alla posizione 3 tToS indica già che d proviene da m.

Ogni posizione richiede alcune operazioni sulle mappe, quindi il tempo è O(n). Il codice di ogni carattere è inferiore a 128, quindi ogni mappa può essere un array di 128 elementi: spazio O(1). Le versioni in R e Swift copiano prima le stringhe in array di codici, operazione che richiede O(n).

Algoritmo

Crea due mappe vuote, sToT e tToS.
Per ogni indice i, assegna a = s[i] e b = t[i].
Se a non è in sToT e b non è in tToS, associa a a b e b ad a.
Altrimenti, se sToT[a] non è b oppure tToS[b] non è a, restituisci false.
Dopo l'ultimo indice, restituisci 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

Trappole e casi limite

Mantenere un'unica mappa da s a t. Accetta moon e deed, e ab e aa.
Confrontare quante volte compare ogni carattere. abcabc e xyzxzy usano entrambi tre caratteri due volte ciascuno, eppure la seconda b si trova sopra z, mentre la prima si trovava sopra y.
Considerare uguali le maiuscole e le minuscole. aA contiene due caratteri diversi, quindi non può diventare bb.
Dimensionare gli array delle mappe solo per a fino a z. Le lettere maiuscole e le cifre non rientrano in questo intervallo; usa il codice carattere completo come indice, con 128 elementi.

Domande frequenti4

Qual è la complessità temporale delle stringhe isomorfe?

La soluzione con due mappe legge ogni posizione una volta, quindi ha una complessità temporale di O(n). Le mappe contengono al massimo una voce per ogni carattere possibile, 62 lettere e cifre, quindi lo spazio aggiuntivo è O(1). Confrontare ogni coppia di posizioni richiede O(n²).

Perché ti servono due mappe hash per le stringhe isomorfe?

Una mappa da s a t rileva un carattere di s rinominato in due modi. Non può rilevare due caratteri di s rinominati nello stesso carattere, come in ab e aa. La mappa da t a s rileva quel caso.

L'isomorfismo è simmetrico?

Sì. Una rinomina uno a uno può essere annullata, quindi se s viene rinominato in t, invertendo ogni nome si riporta t a s. isIsomorphic(s, t) e isIsomorphic(t, s) concordano sempre.

In quale altro modo puoi verificare se due stringhe sono isomorfe?

Sostituisci ogni carattere con la posizione in cui appare per la prima volta e confronta i risultati. noon e deed diventano entrambi 0 1 1 0, mentre moon diventa 0 1 1 3. Richiede inoltre un tempo O(n), con memoria O(n) per i due schemi.

def isIsomorphic(s, t):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomenti

s = "noon"
t = "deed"

Output atteso

true