Is Subsequence

Q: Qual è la complessità temporale di Is Subsequence?

La soluzione a due puntatori viene eseguita in tempo O(n + m) , dove n e m sono le lunghezze di s e t , con memoria aggiuntiva O(1) . Il ciclo si interrompe dopo al massimo m passaggi. La tabella dei prefissi richiede un tempo O(n × m) .

Q: In che modo Is Subsequence è correlato alla sottosequenza comune più lunga?

s è una sottosequenza di t esattamente quando la loro sottosequenza comune più lunga ha lunghezza n , ovvero la lunghezza di s . La tabella dei prefissi del primo approccio è quella che costruisci per quel problema. Qui devi solo sapere se tutta s trova posto, quindi è sufficiente una passata greedy.

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, e false altrimenti. Per esempio, ace è una sottosequenza di abcde, ma aec no.

Funzione

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

sstring: la stringa da cercare
tstring: la stringa da cui eliminare lettere
Restituisceboolean: vero se s può essere letta all'interno di t in ordine, eventualmente con spazi

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 contiene 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.

Per approfondire

Se t rimane fisso e confronti un milione di stringhe s con esso, come prepareresti t affinché ogni confronto sia più veloce che leggere tutto 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, il che suggerisce di provare molte posizioni per s. Non è necessario: abbinare ogni lettera di s nel primo punto in cui può andare non è mai peggio di qualsiasi altra scelta, quindi basta una passata da sinistra a destra con due puntatori per deciderlo.

Programmazione dinamica sui prefissi

Corretto, ma non termina sui test più grandi

Intuizione

Indichiamo con dp[i][j] se le prime i lettere di s rientrano nelle prime j lettere di t. Vi rientrano se vi rientravano già senza t[j-1], oppure se s[i-1] è uguale a t[j-1] e le prime i-1 lettere rientrano in t[:j-1]. Il prefisso vuoto rientra ovunque e la riga i legge solo la riga i-1, quindi bastano due righe di lunghezza m+1.

La tabella riempie ogni cella: con s di 25,000 lettere e t di 50,000, sono 1.25 × 10^9 celle.

Algoritmo

Crea una riga prev di m+1 valori, tutti true: una s vuota è compatibile con 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 corrispondenza greedy

Intuizione

Mantieni un puntatore i alla prossima lettera di s che ti serve e prendi la prima copia che incontri in t. Questa scelta è sicura. Se una disposizione valida usa una copia successiva di s[i], sostituirla con la copia più vicina all'inizio mantiene l'ordine e lascia più caratteri di t per il resto di s. Quindi, se esiste una disposizione, quella greedy la trova.

Il ciclo legge ogni lettera di t al massimo una volta e mantiene due indici: tempo O(n + m) e memoria O(1).

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

Cercare ogni lettera di s in un punto qualsiasi di t, invece che dopo la corrispondenza precedente. Questo accetta aec in abcde.
Usare due volte la stessa lettera. noon non è una sottosequenza di moon: la sua unica n, all'indice 3, non può essere sia la prima sia l'ultima lettera.
Restituire se j ha raggiunto la fine di t. Il ciclo spesso termina lì, indipendentemente dal fatto che s sia stata trovata o meno; solo i te lo dice.
Non fermarsi quando t finisce. abc confrontato con ab deve restituire false.
Leggere s[i] dopo che i ha raggiunto la fine di s. In Python o Java quella lettura genera un errore, quindi controlla i prima di confrontare.

Domande frequenti3

Qual è la complessità temporale di Is Subsequence?

La soluzione a due puntatori viene eseguita in tempo O(n + m), dove n e m sono le lunghezze di s e t, con memoria aggiuntiva O(1). Il ciclo si interrompe dopo al massimo m passaggi. La tabella dei prefissi richiede un tempo O(n × m).

In che modo Is Subsequence è correlato alla sottosequenza comune più lunga?

s è una sottosequenza di t esattamente quando la loro sottosequenza comune più lunga ha lunghezza n, ovvero la lunghezza di s. La tabella dei prefissi del primo approccio è quella che costruisci per quel problema. Qui devi solo sapere se tutta s trova posto, quindi è sufficiente una passata greedy.

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.

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

Test #1

Test #2

Test #3

Argomenti

s = "ace"
t = "abcde"

Output atteso

true