Valid Anagram

Q: Qual è la complessità temporale di Valid Anagram?

Contare le lettere richiede O(n) tempo e O(1) spazio aggiuntivo, perché l’array di contatori ha 26 elementi indipendentemente dalla lunghezza delle stringhe. Ordinare entrambe le stringhe richiede O(n log n) tempo e di solito O(n) spazio per le copie ordinate.

Q: È meglio ordinare o contare quando si verifica se due parole sono anagrammi?

Il conteggio è più veloce in teoria, O(n) rispetto a O(n log n) , e può fermarsi non appena una lettera viene usata troppe volte. L'ordinamento è più breve da scrivere e funziona con qualsiasi alfabeto senza modifiche. In un colloquio, menziona prima l'ordinamento e poi miglioralo con il conteggio.

FacileHashing Ordinamento

+10

Due stringhe sono anagrammi quando una è una riorganizzazione dell’altra: usano le stesse lettere e ciascuna lettera lo stesso numero di volte. Ti vengono date due stringhe s e t composte da lettere inglesi minuscole. Restituisci true se t è un anagramma di s, e false altrimenti.

Funzione

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

sstring: la prima stringa, lettere minuscole
tstring: la stringa con cui confrontare s
Restituisceboolean: vero se t utilizza esattamente le lettere di s, ciascuna lo stesso numero di volte

Vincoli

1 ≤ s.length, t.length ≤ 2 × 10⁴
s e t contengono solo lettere inglesi minuscole (a–z).
Le due lunghezze possono essere diverse.

Esempi

Input: s = "listen"t = "silent"
Output: true
Spiegazione: Entrambe le parole contengono una e, una i, una l, una n, una s e una t, quindi silent è listen con le lettere riordinate.

Input: s = "aabb"t = "abbb"
Output: false
Spiegazione: Le lunghezze coincidono ed entrambi usano solo a e b, ma aabb ha due a e abbb ne ha una. Le quantità devono coincidere, non solo le lettere.

Input: s = "cat"t = "cast"
Output: false
Spiegazione: cast ha quattro lettere e cat ne ha tre, quindi nessuna riorganizzazione di cat può formare questa parola.

+19 test nascosti all’invio

Per approfondire

Che cosa succederebbe se le stringhe potessero contenere qualsiasi carattere Unicode invece di a e z? Come modificheresti il conteggio?

Suggerimenti

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

0 di 3 aperti

Soluzione

Un anagramma conserva il numero di occorrenze delle lettere e scarta l’ordine. Quindi ti serve un riepilogo di ogni stringa che dimentichi dove si trovavano le lettere, ma ricordi quante ce ne sono per ciascuna. L’ordinamento crea quel riepilogo in O(n log n); una tabella di 26 contatori lo crea in un solo passaggio.

Ordina entrambe le stringhe

Intuizione

L'ordinamento mette le lettere di una stringa in ordine alfabetico e cancella la posizione iniziale di ciascuna. listen viene ordinata in eilnst, così come silent, quindi sono anagrammi. aabb resta aabb e abbb resta abbb; differiscono all'indice 1, quindi non sono anagrammi.

Il test funziona in entrambe le direzioni. Se t è una permutazione di s, le due stringhe contengono le stesse lettere lo stesso numero di volte, quindi l'ordinamento produce la stessa sequenza. Se le sequenze ordinate sono uguali, t usa esattamente le lettere di s.

Confronta prima le lunghezze: stringhe di lunghezze diverse non sono mai anagrammi, e puoi saltare entrambi gli ordinamenti. L'ordinamento richiede un tempo di O(n log n) e la maggior parte dei linguaggi ordina una copia dei caratteri, usando O(n) spazio aggiuntivo. Con n = 2 × 10^4 è veloce, ma l'approccio basato sul conteggio richiede meno lavoro.

Algoritmo

Se le lunghezze di s e t sono diverse, restituisci false.
Copia i caratteri di ciascuna stringa in un array.
Ordina entrambi gli array.
Restituisci true se gli array ordinati sono uguali, elemento per elemento.

def isAnagram(s, t):
    if len(s) != len(t):
        return False
    return sorted(s) == sorted(t)

Conta ogni lettera

Intuizione

Possono comparire solo 26 lettere, quindi tieni un contatore per ogni lettera in un array di 26 elementi, con indice 0 per a e indice 25 per z. L’indice di una lettera è il suo codice carattere meno il codice di a. Scorri s e aggiungi 1 al contatore di ogni lettera, poi scorri t e sottrai 1.

Puoi fermarti in anticipo: un contatore inferiore a 0 significa che t ha usato quella lettera più spesso di quanto l’abbia usata s. Per aabb e abbb, dopo s i contatori indicano a: 2 e b: 2. Poi t usa b tre volte; la terza volta porta b a -1 e restituisci subito false.

Perché è sufficiente che «nessun contatore sia diventato negativo»? Le lunghezze sono uguali, quindi dopo averle percorse entrambe la somma dei contatori è 0. Se nessuno è negativo, un valore positivo non avrebbe nulla con cui compensarsi, quindi tutti i contatori sono 0 e le quantità corrispondono. Ecco perché il controllo della lunghezza è necessario, non è solo una scorciatoia.

Ogni stringa viene letta una volta, quindi il tempo è O(n). L’array contiene sempre 26 numeri, indipendentemente dalla lunghezza, quindi lo spazio aggiuntivo è O(1).

Algoritmo

Se le lunghezze di s e t sono diverse, restituisci false.
Crea un array di 26 zeri.
Per ogni lettera di s, aggiungi 1 al suo contatore.
Per ogni lettera di t, sottrai 1 dal suo contatore; se scende sotto 0, restituisci false.
Restituisci true.

def isAnagram(s, t):
    if len(s) != len(t):
        return False
    counts = [0] * 26  # counts[0] is 'a', counts[25] is 'z'
    for ch in s:
        counts[ord(ch) - ord("a")] += 1
    for ch in t:
        index = ord(ch) - ord("a")
        counts[index] -= 1
        if counts[index] < 0:
            return False  # t uses this letter more often than s
    return True

Trappole e casi limite

La maggior parte delle risposte sbagliate dipende dal controllare quali lettere compaiono invece di quante volte, oppure dal saltare il controllo della lunghezza.

Confrontare gli insiemi di lettere. aabb e abbb usano entrambi esattamente a e b, ma non sono anagrammi.
Controllare che ogni lettera di t compaia da qualche parte in s senza eliminarla. aab e abb superano questo test in entrambe le direzioni.
Saltare il controllo della lunghezza nella versione con conteggio. Con s = ab e t = a, nessun contatore scende sotto 0, quindi il codice restituirebbe erroneamente true.
Usare il codice carattere grezzo per indicizzare l'array dei contatori. a corrisponde a 97, ben oltre la fine di un array di 26 elementi; sottrai prima il codice di a. In Lua e R aggiungi 1, poiché i loro array iniziano dall'indice 1.

Domande frequenti4

Qual è la complessità temporale di Valid Anagram?

Contare le lettere richiede O(n) tempo e O(1) spazio aggiuntivo, perché l’array di contatori ha 26 elementi indipendentemente dalla lunghezza delle stringhe. Ordinare entrambe le stringhe richiede O(n log n) tempo e di solito O(n) spazio per le copie ordinate.

È meglio ordinare o contare quando si verifica se due parole sono anagrammi?

Il conteggio è più veloce in teoria, O(n) rispetto a O(n log n), e può fermarsi non appena una lettera viene usata troppe volte. L'ordinamento è più breve da scrivere e funziona con qualsiasi alfabeto senza modifiche. In un colloquio, menziona prima l'ordinamento e poi miglioralo con il conteggio.

Come si verificano gli anagrammi che contengono caratteri Unicode?

Sostituisci l’array di 26 contatori con una mappa hash da carattere a conteggio. Aggiungi 1 per ogni carattere di s, sottrai 1 per ogni carattere di t e verifica che ogni conteggio termini a 0. Leggi le stringhe carattere per carattere, non byte per byte, in modo che un carattere memorizzato su più byte venga contato una sola volta.

Perché usare un solo array di contatori invece di due?

Vanno bene anche due array, uno per stringa: conta ogni stringa, poi confronta gli array. Un array che aumenta per s e diminuisce per t usa la metà della memoria e ti permette di restituire false non appena un contatore diventa negativo, senza un ciclo di confronto finale.

Python

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

Casi di test

Caso 1

Caso 2

Caso 3

Input

s = "listen"
t = "silent"

Atteso

true