Is Subsequence

Q: Perché l’approccio greedy con due puntatori funziona per Is Subsequence?

Abbinare una lettera di s nel suo primo posto possibile in t lascia la parte rimanente di t più lunga possibile per le lettere restanti. Qualsiasi posizionamento che usa una copia successiva può essere modificato per usare quella precedente senza interrompere l’ordine, quindi, se esiste un posizionamento, quello greedy lo trova.

Q: Come controlli rapidamente molte stringhe con lo stesso t?

Prepara t una volta: per ogni lettera, memorizza l’elenco ordinato degli indici in cui compare. Per posizionare s[i] , esegui una ricerca binaria nell’elenco di quella lettera per trovare il primo indice successivo alla corrispondenza precedente. Ogni verifica costa quindi O(n log m) invece di O(m) .

FacileDue puntatori

+10

Ti vengono date due stringhe, s e t. Restituisci true se puoi trasformare t in s eliminando alcune delle sue lettere (eventualmente nessuna), mantenendo l’ordine delle lettere rimanenti; altrimenti restituisci false. Ad esempio, ace è una sottosequenza di abcde, ma aec non lo è.

Funzione

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

sstring: la stringa da cercare
tstring: la stringa da cui eliminare le lettere
Restituisceboolean: true se s può essere letto all'interno di t in ordine, eventualmente con delle lacune

Vincoli

1 ≤ s.length ≤ 3 × 10⁴
1 ≤ t.length ≤ 5 × 10⁴
s e t contengono solo lettere minuscole inglesi.

Esempi

Input: s = "ace"t = "abcde"
Output: true
Spiegazione: Elimina b e d da abcde e rimane ace, nello stesso ordine.

Input: s = "aec"t = "abcde"
Output: false
Spiegazione: t ha tutte e tre le lettere, ma l’unica c si trova prima dell’unica e. Dopo aver usato la e all’indice 4, non rimane alcuna c alla sua destra.

Input: s = "moon"t = "monsoon"
Output: true
Spiegazione: Usa la m all'indice 0, le o agli indici 1 e 4 e la n all'indice 6 di monsoon. Le lettere in mezzo vengono eliminate.

+20 test nascosti all’invio

Per approfondire

Supponiamo che t resti invariata e che tu debba confrontare con essa un milione di stringhe diverse s. Come prepareresti t per rendere ogni controllo più veloce che rileggere ogni volta tutta t?

Suggerimenti

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

0 di 3 aperti

Soluzione

Una sottosequenza può saltare lettere di t in qualsiasi punto, quindi potrebbe sembrare necessario provare molti modi per inserire s dentro t. Non è così. Abbinare ogni lettera di s nel primo punto possibile non è mai peggio di qualsiasi altra scelta e trasforma la ricerca in un'unica scansione da sinistra a destra con due puntatori.

Programmazione dinamica sui prefissi

Corretto, ma non termina sui test più grandi

Intuizione

Poni una domanda più semplice: le prime i lettere di s si possono trovare tra le prime j lettere di t? Chiama la risposta dp[i][j]. Se si possono trovare tra le lettere di t[:j-1], si possono trovare anche tra quelle di t[:j], perché puoi eliminare t[j-1]. Se s[i-1] è uguale a t[j-1], puoi usare anche quella lettera e, in tal caso, le prime i-1 lettere di s devono potersi trovare tra le lettere di t[:j-1]. Quindi dp[i][j] = dp[i][j-1] or (s[i-1] == t[j-1] and dp[i-1][j-1]), e il prefisso vuoto di s si può trovare ovunque.

La riga i legge solo la riga i-1, quindi bastano due righe di lunghezza m+1. La risposta è l’ultima cella dell’ultima riga.

È la stessa tabella che costruisci per la sottosequenza comune più lunga, ed è corretta, ma riempie tutte le celle. Con s di 25,000 lettere e t di 50,000, si tratta di 1.25 × 10^9 celle, molte più di quelle necessarie per un’unica scansione delle due stringhe.

Algoritmo

Crea una riga prev di m+1 valori, tutti true: una s vuota si adatta a ogni prefisso di t.
Per ogni i da 1 a n, crea una riga cur con cur[0] = false.
Per ogni j da 1 a m, imposta cur[j] su cur[j-1], oppure su prev[j-1] quando s[i-1] è uguale a t[j-1].
Sostituisci prev con cur.
Restituisci prev[m].

def isSubsequence(s, t):
    n, m = len(s), len(t)
    # prev[j]: the first i-1 letters of s fit inside t[:j]. An empty s fits anywhere.
    prev = [True] * (m + 1)
    for i in range(1, n + 1):
        cur = [False] * (m + 1)
        for j in range(1, m + 1):
            cur[j] = cur[j - 1] or (s[i - 1] == t[j - 1] and prev[j - 1])
        prev = cur
    return prev[m]

Due puntatori con abbinamento greedy

Intuizione

Leggi t da sinistra a destra e mantieni un puntatore i alla prossima lettera di s che devi ancora trovare. Quando t[j] è uguale a s[i], usala e fai avanzare i. In ogni caso, fai avanzare j. Se i raggiunge la fine di s, ogni lettera ha trovato il proprio posto nell'ordine corretto.

Perché è sicuro scegliere la prima corrispondenza? Supponiamo che una disposizione valida usi una copia successiva di s[i]. Sostituirla con la copia più vicina all'inizio mantiene l'ordine e lascia più caratteri di t a destra per il resto di s, quindi la scelta greedy non fa mai perdere una disposizione esistente. Per moon in monsoon, il puntatore prende la o all'indice 1, salta n e s, prende la o all'indice 4 e si ferma sulla n all'indice 6.

j visita ogni lettera di t una sola volta e i avanza soltanto, quindi il ciclo viene eseguito al massimo m volte. Gli bastano due indici come memoria.

Algoritmo

Imposta i = 0 per s e j = 0 per t.
Finché entrambi gli indici sono all'interno delle rispettive stringhe, confronta s[i] con t[j].
Se sono uguali, incrementa i.
Incrementa j in ogni caso.
Restituisci se i è uguale alla lunghezza di s.

def isSubsequence(s, t):
    i = j = 0
    while i < len(s) and j < len(t):
        if s[i] == t[j]:
            i += 1
        j += 1
    return i == len(s)

Trappole e casi limite

Il ciclo a due puntatori è breve e i suoi bug si annidano nei casi limite.

Cercare ogni lettera di s ovunque in t invece che dopo la corrispondenza precedente. Così si accetta aec in abcde, anche se l’ordine non è rispettato.
Usare due volte la stessa lettera. noon non è una sottosequenza di moon: moon contiene una sola n, all’indice 3, e non può essere sia la prima sia l’ultima lettera di noon.
Restituire se j ha raggiunto la fine di t. Spesso il ciclo termina lì, indipendentemente dal fatto che s sia stata trovata; solo i te lo dice.
Dimenticare che s può essere più lunga di t. Confrontando abc con ab si deve restituire false, cosa che il ciclo fa purché si fermi quando t termina.
Leggere s[i] dopo che i ha raggiunto la fine di s. In Python o Java questa lettura genera un’eccezione, quindi controlla i prima del confronto.

Domande frequenti4

Qual è la complessità temporale di Is Subsequence?

La soluzione con due puntatori ha una complessità temporale di O(n + m), dove n e m sono le lunghezze di s e t, e usa O(1) di memoria aggiuntiva. In pratica, il ciclo si interrompe dopo al massimo m passaggi. La tabella dei prefissi richiede O(n × m) di tempo.

Perché l’approccio greedy con due puntatori funziona per Is Subsequence?

Abbinare una lettera di s nel suo primo posto possibile in t lascia la parte rimanente di t più lunga possibile per le lettere restanti. Qualsiasi posizionamento che usa una copia successiva può essere modificato per usare quella precedente senza interrompere l’ordine, quindi, se esiste un posizionamento, quello greedy lo trova.

Come controlli rapidamente molte stringhe con lo stesso t?

Prepara t una volta: per ogni lettera, memorizza l’elenco ordinato degli indici in cui compare. Per posizionare s[i], esegui una ricerca binaria nell’elenco di quella lettera per trovare il primo indice successivo alla corrispondenza precedente. Ogni verifica costa quindi O(n log m) invece di O(m).

Qual è la differenza tra una sottosequenza e una sottostringa?

Una sottostringa è un blocco di lettere consecutive, mentre una sottosequenza può saltare delle lettere, purché l’ordine rimanga lo stesso. ace è una sottosequenza di abcde, ma non una sua sottostringa. Ogni sottostringa è una sottosequenza, ma non vale il contrario.

Python

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

Casi di test

Caso 1

Caso 2

Caso 3

Input

s = "ace"
t = "abcde"

Atteso

true