Permutation in String

Q: Qual è la complessità temporale di Permutation in String?

Con una finestra scorrevole è O(m + n) , dove m è la lunghezza di s1 e n è la lunghezza di s2 . Conti s1 una volta, poi ogni lettera di s2 entra nella finestra una volta e ne esce una volta. Ricontare ogni finestra da zero costa invece O(n · m) .

Q: Permutazione in una stringa equivale a trovare un anagramma all'interno di una stringa?

Sì. Una permutazione di s1 è un suo anagramma, quindi la domanda è se qualche sottostringa di s2 di lunghezza m sia un anagramma di s1 . Il controllo dell’anagramma tra due stringhe intere confronta una sola volta il numero di occorrenze delle lettere; qui lo stesso confronto viene eseguito su una finestra che scorre lungo s2 .

Q: Perché la finestra scorrevole ha qui una dimensione fissa?

Ogni permutazione di s1 ha esattamente m lettere, quindi solo le finestre di lunghezza m possono corrispondere. Problemi come quello della sottostringa più lunga senza ripetizioni fanno crescere e restringere la finestra; qui entrambi i bordi si spostano insieme, un passo alla volta.

MedioFinestra scorrevole Hashing

+10

Una permutazione di una stringa usa le stesse lettere in qualsiasi ordine, ciascuna tante volte quante nella stringa originale: tar, rat e art sono permutazioni l'una dell'altra. Ti vengono date due stringhe s1 e s2 composte da lettere inglesi minuscole. Restituisci true se una qualche permutazione di s1 compare in s2 come sottostringa (una sequenza di caratteri consecutivi), e false altrimenti.

Funzione

checkInclusion(s1: string, s2: string) → boolean

s1string: le lettere da riordinare
s2string: la stringa in cui cercare
Restituisceboolean: vero se una sottostringa di s2 è una permutazione di s1

Vincoli

1 ≤ s1.length ≤ 2 × 10⁴
1 ≤ s2.length ≤ 5 × 10⁴
s1 e s2 contengono solo lettere inglesi minuscole (da a a z).
s1 può essere più lunga di s2.

Esempi

Input: s1 = "tar"s2 = "smartphone"
Output: true
Spiegazione: La sottostringa art agli indici da 2 a 4 di smartphone contiene una a, una r e una t, le stesse lettere di tar.

Input: s1 = "noon"s2 = "onion"
Output: false
Spiegazione: Le sottostringhe di lunghezza 4 sono onio e nion. noon richiede due n e due o, e ogni finestra contiene una i al posto di una di queste. Ogni lettera di noon è presente in onion, ma nessuna finestra contiene le quantità corrette.

Input: s1 = "abcd"s2 = "dcb"
Output: false
Spiegazione: Qualsiasi permutazione di abcd ha 4 lettere, mentre dcb ne ha solo 3, quindi non può contenerne una.

+17 test nascosti all’invio

Per approfondire

Riesci a restituire ogni indice di s2 da cui inizia una permutazione di s1, sempre in tempo O(m + n)?

Suggerimenti

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

0 di 3 aperti

Soluzione

Elencare le permutazioni di s1 è inutile: 10 lettere hanno già 3,628,800 possibili ordinamenti. La soluzione è smettere di preoccuparsi dell’ordine. Una sottostringa di s2 è una permutazione di s1 esattamente quando ha la stessa lunghezza m e lo stesso numero di ogni lettera. Quindi ogni possibile candidata è una finestra della stessa lunghezza fissa, e puoi far scorrere una finestra su s2, aggiornando il conteggio delle lettere aggiungendone una e rimuovendone una a ogni passaggio.

Conta ogni finestra da capo

Corretto, ma non termina sui test più grandi

Intuizione

La lettura letterale, costruire ogni permutazione di s1 e cercarla, fallisce subito: 20 lettere hanno più di 2 × 10^18 ordinamenti. Invece, ribalta la domanda. Una sottostringa di s2 è una permutazione di s1 quando contiene esattamente m lettere e usa ogni lettera tante volte quante ne usa s1. L’ordine al suo interno non conta mai.

Quindi conta una volta le lettere di s1 in una tabella di 26 numeri, con indice 0 per a e 25 per z. Poi considera ogni sottostringa di s2 di lunghezza m, conta le sue lettere in una tabella nuova e confronta le due tabelle. Per tar in smartphone, le finestre sono sma, mar, art e così via, e art corrisponde: una a, una r, una t.

È corretto perché considera ogni possibile candidata. È lento perché le finestre adiacenti condividono m-1 lettere e le riconti tutte. Con m = 15,000 e n = 50,000 ci sono 35,001 finestre di 15.000 lettere ciascuna, circa 5 × 10^8 passaggi.

Algoritmo

Se s1 è più lunga di s2, restituisci false.
Conta le lettere di s1 in una tabella need di 26 zeri.
Per ogni indice iniziale da 0 a n-m, conta le lettere dei m caratteri a partire da quell'indice in una nuova tabella.
Se quella tabella è uguale a need, restituisci true.
Dopo l'ultima finestra, restituisci false.

def checkInclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    need = [0] * 26  # need[0] is 'a', need[25] is 'z'
    for ch in s1:
        need[ord(ch) - 97] += 1
    for start in range(n - m + 1):
        # Count the letters of s2[start : start + m] from scratch
        window = [0] * 26
        for i in range(start, start + m):
            window[ord(s2[i]) - 97] += 1
        if window == need:
            return True
    return False

Fai scorrere la finestra e confronta i conteggi 26

Intuizione

Due finestre adiacenti differiscono solo per due lettere. Passando da mar a art, si rimuove la m a sinistra e si aggiunge la t a destra. Quindi mantieni una tabella per la finestra corrente e aggiornala con un +1 e un -1 a ogni passaggio, invece di contare di nuovo le lettere m.

Riempi need usando s1 e window usando le prime m lettere di s2, quindi confrontale. Poi, per ogni i da m a n-1, aggiungi s2[i], rimuovi s2[i-m] e confronta di nuovo. La finestra ora è s2[i-m+1..i] e contiene ancora m lettere.

Ogni passaggio richiede due aggiornamenti e il confronto di 26 numeri, qualunque sia il valore di m. Con l'input più grande, sono circa 26 × 50,000 = 1.3 × 10^6 operazioni, lineari rispetto alla lunghezza di s2. Questa è la soluzione che la maggior parte degli intervistatori si aspetta.

Algoritmo

Se s1 è più lunga di s2, restituisci false.
Conta s1 in need e le prime m lettere di s2 in window.
Se le due tabelle sono uguali, restituisci true.
Per ogni i da m a n-1: aggiungi 1 per s2[i], sottrai 1 per s2[i-m] e restituisci true se le tabelle sono uguali.
Restituisci false.

def checkInclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    need = [0] * 26
    window = [0] * 26
    for i in range(m):
        need[ord(s1[i]) - 97] += 1
        window[ord(s2[i]) - 97] += 1  # the first window is s2[0 : m]
    if window == need:
        return True
    for i in range(m, n):
        window[ord(s2[i]) - 97] += 1      # s2[i] enters on the right
        window[ord(s2[i - m]) - 97] -= 1  # s2[i - m] leaves on the left
        if window == need:
            return True
    return False

Fai scorrere la finestra e tieni traccia delle lettere non bilanciate

Intuizione

Confrontare 26 numeri a ogni passaggio ripete del lavoro, perché un passaggio modifica solo due di essi. Tieni invece una sola tabella balance: balance[c] indica quante copie della lettera c contiene s1, meno quante ne contiene la finestra. La finestra è una permutazione di s1 esattamente quando tutti i 26 valori di balance sono 0. Accanto alla tabella, tieni unbalanced, il numero di lettere il cui valore di balance non è 0, e restituisci true nel momento in cui raggiunge 0.

La registrazione dei valori segue una regola. Prima di modificare balance[c], se il suo valore è 0, la lettera sta per perdere l’equilibrio, quindi incrementa unbalanced di 1. Dopo la modifica, se il suo valore è 0, la lettera ha raggiunto l’equilibrio, quindi decrementa unbalanced di 1. Una lettera che entra nella finestra riduce il suo valore di balance di 1; una lettera che ne esce lo aumenta di 1. Un valore di balance che passa da 2 a 1 non attiva nessuno dei due controlli, ed è corretto: la lettera era sbilanciata e lo è ancora.

Seguiamo tar e smartphone. I valori di balance iniziano così: a: 1, r: 1, t: 1, quindi unbalanced è 3. s e m entrano e lo portano a 5, poi entra a e porta il valore di a a 0: 4. Entra r (3) mentre esce s (2). Entra t (1) mentre esce m (0), e la finestra art è la risposta.

Puoi verificare unbalanced == 0 fin dalla prima lettera. Finché la finestra contiene meno di m lettere, la somma dei valori di balance è positiva, quindi almeno uno di essi non è 0. Ogni passaggio richiede una quantità fissa di lavoro, quindi l’intera scansione è O(m + n), e la tabella contiene sempre 26 numeri, quindi lo spazio è O(1).

Algoritmo

Se s1 è più lunga di s2, restituisci false.
Conta s1 in balance e imposta unbalanced sul numero di lettere con un bilancio diverso da 0.
Per ogni indice i di s2, sottrai 1 dal bilancio di s2[i], aggiungendo 1 a unbalanced se quel bilancio era 0 e sottraendo 1 se diventa 0.
Se i ≥ m, aggiungi 1 al bilancio di s2[i-m] con lo stesso aggiornamento.
Se unbalanced è 0, restituisci true. Dopo il ciclo, restituisci false.

def checkInclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    # balance[c]: copies of letter c in s1 minus copies in the window
    balance = [0] * 26
    for ch in s1:
        balance[ord(ch) - 97] += 1
    unbalanced = sum(1 for b in balance if b != 0)
    for i in range(n):
        # s2[i] enters the window on the right
        c = ord(s2[i]) - 97
        if balance[c] == 0:
            unbalanced += 1
        balance[c] -= 1
        if balance[c] == 0:
            unbalanced -= 1
        # s2[i - m] leaves on the left once the window would pass m letters
        if i >= m:
            c = ord(s2[i - m]) - 97
            if balance[c] == 0:
                unbalanced += 1
            balance[c] += 1
            if balance[c] == 0:
                unbalanced -= 1
        if unbalanced == 0:
            return True
    return False

Trappole e casi limite

La maggior parte delle risposte sbagliate deriva dai bordi della finestra o dal controllare quali lettere compaiono invece di quante volte.

Controllare solo che ogni lettera di s1 sia nella finestra. onio contiene tutte le lettere di noon, ma non è una sua permutazione. Confronta le occorrenze.
Rimuovere la lettera sbagliata. Quando s2[i] entra, la lettera che esce è s2[i-m], quindi la finestra diventa s2[i-m+1..i]. Rimuovere s2[i-m+1] lascia una finestra di m-1 lettere.
Saltare la prima finestra. Se confronti solo dopo aver fatto scorrere la finestra, una permutazione all'indice 0 non verrà mai trovata.
Dimenticare il caso in cui s1 è più lunga di s2. In Rust, n - m con lunghezze senza segno va in underflow, e in Swift l'intervallo 0...(n - m) causa un arresto anomalo. Restituisci prima false.
Confrontare array con == in un linguaggio in cui questo confronta i riferimenti. In JavaScript e Dart, due array diversi non sono mai ==; in Java usa Arrays.equals.

Domande frequenti4

Qual è la complessità temporale di Permutation in String?

Con una finestra scorrevole è O(m + n), dove m è la lunghezza di s1 e n è la lunghezza di s2. Conti s1 una volta, poi ogni lettera di s2 entra nella finestra una volta e ne esce una volta. Ricontare ogni finestra da zero costa invece O(n · m).

Permutazione in una stringa equivale a trovare un anagramma all'interno di una stringa?

Sì. Una permutazione di s1 è un suo anagramma, quindi la domanda è se qualche sottostringa di s2 di lunghezza m sia un anagramma di s1. Il controllo dell’anagramma tra due stringhe intere confronta una sola volta il numero di occorrenze delle lettere; qui lo stesso confronto viene eseguito su una finestra che scorre lungo s2.

Perché la finestra scorrevole ha qui una dimensione fissa?

Ogni permutazione di s1 ha esattamente m lettere, quindi solo le finestre di lunghezza m possono corrispondere. Problemi come quello della sottostringa più lunga senza ripetizioni fanno crescere e restringere la finestra; qui entrambi i bordi si spostano insieme, un passo alla volta.

Posso usare una mappa hash invece di un array di 26 contatori?

Sì, e te ne serve uno se le stringhe possono contenere qualsiasi carattere. Se contengono solo lettere minuscole, un array di 26 elementi è più veloce e usa uno spazio costante. Con una mappa, elimina una chiave quando il suo conteggio scende a 0, in modo che due mappe con le stesse lettere risultino uguali, oppure mantieni il contatore unbalanced dell’approccio precedente, che funziona allo stesso modo con una mappa.

Python

def checkInclusion(s1, s2):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

s1 = "tar"
s2 = "smartphone"

Atteso

true

Permutation in String

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Conta ogni finestra da capo

Fai scorrere la finestra e confronta i conteggi 26

Fai scorrere la finestra e tieni traccia delle lettere non bilanciate

Trappole e casi limite

Domande frequenti4

Problemi simili