Regular Expression Matching

Q: Qual è la complessità temporale della corrispondenza con le espressioni regolari?

La soluzione con tabella richiede un tempo O(n × m) , dove n è la lunghezza di s e m la lunghezza di p , perché ogni cella legge al massimo altre due celle. Richiede O(n × m) di memoria per la tabella completa, oppure O(m) usando due righe. La ricorsione semplice può richiedere un tempo esponenziale con schemi contenenti molti asterischi.

Q: Perché una cella con una stella legge la cella sopra e non quella diagonale?

La cella sopra, dp[i-1][j] , segue lo stesso schema con una lettera in meno di s , e l’asterisco è ancora presente. Quindi, dopo aver «mangiato» s[i-1] , può mangiare anche s[i-2] e così via risalendo la colonna. La cella diagonale dp[i-1][j-2] rimuove l’asterisco dopo una lettera, consentendo esattamente una copia invece di un numero qualsiasi.

DifficileProgrammazione dinamica Ricorsione

+10

Ricevi una stringa s e un pattern p. Nel pattern, una lettera corrisponde alla stessa lettera, un punto . corrisponde a una qualsiasi lettera e un asterisco * indica zero o più ripetizioni dell’elemento che lo precede, che può essere una lettera o un punto. Restituisci true se il pattern corrisponde all’intera s, non solo a una sua parte, e false altrimenti.

Funzione

isMatch(s: string, p: string) → boolean

sstring: la stringa da confrontare, solo lettere minuscole
pstring: lo schema di lettere, punti e asterischi
Restituisceboolean: true se p corrisponde a tutto s, false altrimenti

Vincoli

1 ≤ s.length ≤ 1000
1 ≤ p.length ≤ 1000
s contiene solo lettere minuscole inglesi.
p contiene solo lettere inglesi minuscole, . e *.
Ogni * segue una lettera o un ., quindi p non inizia mai con * e non ha mai due asterischi consecutivi.

Esempi

Input: s = "moon"p = "mo*n"
Output: true
Spiegazione: o* prende entrambe le lettere o, quindi m, o* e n formano esattamente moon.

Input: s = "tree"p = "t.e"
Output: false
Spiegazione: t.e corrisponde solo a stringhe di tre lettere: t, una lettera qualsiasi, poi e. Corrisponde a tre all’inizio di tree, ma l’ultima e resta fuori, e una corrispondenza deve coprire tutta s.

Input: s = "sky"p = "z*s.*y"
Output: true
Spiegazione: z* prende zero copie di z, s corrisponde a s, .* prende la k e y corrisponde a y. Una lettera con l'asterisco può rappresentare niente, quindi una z che non compare mai in sky non costa nulla.

+29 test nascosti all’invio

Per approfondire

Puoi supportare anche +, una o più copie dell’elemento precedente, con la stessa tabella?

Suggerimenti

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

0 di 3 aperti

Soluzione

Un asterisco può corrispondere a un numero qualsiasi di copie e il numero giusto dipende da ciò che viene dopo. Corrispondere al maggior numero possibile non funziona: con aaa, il modello a*a permette a a* di consumare tutte e tre le lettere e non lascia nulla per l’ultima a. L’idea che risolve il problema è trattare una lettera e il suo asterisco come un’unica unità con due mosse: saltarla oppure farle consumare una lettera rimanendo al suo posto. Una tabella registra se ogni prefisso di s corrisponde a ogni prefisso di p, così ogni scelta viene provata una volta sola e ne bastano due righe.

Abbina da sinistra con la ricorsione

Corretto, ma non termina sui test più grandi

Intuizione

Fai in modo che match(i, j) stabilisca se il suffisso s[i:] corrisponde al suffisso p[j:]. Se il pattern è esaurito, corrisponde solo se è esaurita anche la stringa. Altrimenti calcola first: esiste una lettera s[i] e p[j] è quella lettera oppure un punto.

Ora guarda un carattere avanti. Se p[j+1] è un asterisco, p[j]* è un'unità con due mosse. Può prendere zero copie: salta entrambi i caratteri con match(i, j+2). Oppure, se first è vero, può prendere una copia: consuma s[i] e resta sulla stessa unità con match(i+1, j), pronto a prenderne un'altra. Restare su j è ciò che permette a un singolo asterisco di prendere un numero qualsiasi di lettere, una alla volta. Senza un asterisco, p[j] deve corrispondere esattamente a una lettera: first and match(i+1, j+1).

È lento perché ogni asterisco divide la ricerca in due e spesso si trova un errore solo alla fine. Prendi 30 lettere a contro dieci copie di a* e poi una b. La ricorsione prova ogni modo di distribuire alcune o tutte le 30 lettere a tra i dieci asterischi, circa 8.5 × 10^8 modi, ed effettua circa 2 × 10^9 chiamate prima di poter rispondere false. I test più grandi hanno 1000 lettere. Eppure esistono solo (n+1) × (m+1) coppie diverse (i, j).

Algoritmo

Scrivi match(i, j) per i suffissi che iniziano in i e j.
Se j supera la fine di p, restituisci se i supera la fine di s.
Imposta first in base al fatto che s[i] esista e che p[j] sia s[i] oppure un punto.
Se p[j+1] è un asterisco, restituisci match(i, j+2) oppure first and match(i+1, j).
Altrimenti restituisci first and match(i+1, j+1). La risposta è match(0, 0).

def isMatch(s, p):
    n, m = len(s), len(p)

    def match(i, j):
        # Does s[i:] match p[j:]?
        if j == m:
            return i == n
        first = i < n and p[j] in (s[i], ".")
        if j + 1 < m and p[j + 1] == "*":
            # use p[j] zero times, or let it eat s[i] and stay on the same x*
            return match(i, j + 2) or (first and match(i + 1, j))
        return first and match(i + 1, j + 1)

    return match(0, 0)

Completa una tabella di prefissi

Intuizione

Stato. Sia dp[i][j] a indicare se le prime i lettere di s corrispondono ai primi j caratteri di p. L'indice 0 rappresenta un prefisso vuoto.

Riga e colonna di base. dp[0][0] è true: un pattern vuoto corrisponde a una stringa vuota. La colonna 0 è false nelle righe successive, perché un pattern vuoto non può corrispondere a una lettera. La riga 0 è quella più delicata: un prefisso del pattern corrisponde alla stringa vuota solo se ogni elemento contiene un asterisco, come z* o a*b*. Quindi dp[0][j] è true quando p[j-1] è un asterisco e dp[0][j-2] è true.

Transizioni. Se p[j-1] è una lettera o un punto, deve corrispondere all'ultima lettera s[i-1] e il resto deve corrispondere: dp[i-1][j-1], la diagonale. Se p[j-1] è un asterisco, il suo elemento è x = p[j-2] e l'asterisco ha due possibilità. Zero copie: rimuovi x* dal pattern, dp[i][j-2], due celle a sinistra. Una copia in più: se x corrisponde a s[i-1], quella lettera è una delle copie e lo stesso x* deve ancora corrispondere alla stringa più corta; quindi leggi dp[i-1][j], la cella subito sopra, nella stessa colonna. Ogni copia è un passo in su in quella colonna, ed è così che un singolo asterisco copre un numero qualsiasi di lettere.

Ecco la tabella per sky e z*s.*y, con colonne per i prefissi "", z, z*, z*s, z*s., z*s.*, z*s.*y (T è true, F è false). La riga "" è [T, F, T, F, F, F, F]: solo z* può essere vuoto. La riga s è [F, F, F, T, F, T, F]: s corrisponde a s con z* vuoto sopra di essa sulla diagonale, e poi .* prende zero copie. La riga sk è [F, F, F, F, T, T, F]: la cella per z*s.* diventa true grazie a una copia in più: il punto corrisponde a k, leggendo la T subito sopra. La riga sky è [F, F, F, F, F, T, T]: l'asterisco dopo il punto corrisponde a y allo stesso modo, con un secondo passo in su nella colonna, e poi y corrisponde a y sulla diagonale. L'ultima cella è true.

Ogni cella legge la riga sopra o le celle alla sua sinistra, quindi, compilando la tabella riga per riga, da sinistra a destra, i valori sono già disponibili. Si tratta di (n+1) × (m+1) celle, circa 10^6 nei test più grandi, con un lavoro costante per ciascuna.

Algoritmo

Crea una tabella dp di (n+1) × (m+1) valori false e imposta dp[0][0] su true.
Per j da 2 a m, imposta dp[0][j] su true quando p[j-1] è un asterisco e dp[0][j-2] è true.
Per ogni cella con i ≥ 1 e j ≥ 1, se p[j-1] è un asterisco, impostala su dp[i][j-2] oppure (p[j-2] corrisponde a s[i-1] e dp[i-1][j]).
Altrimenti impostala su (p[j-1] corrisponde a s[i-1]) e dp[i-1][j-1].
Restituisci dp[n][m].

def isMatch(s, p):
    n, m = len(s), len(p)
    # dp[i][j]: do the first i letters of s match the first j characters of p?
    dp = [[False] * (m + 1) for _ in range(n + 1)]
    dp[0][0] = True  # an empty pattern matches an empty string
    for j in range(2, m + 1):
        # an empty string matches only patterns like x*y*z*
        dp[0][j] = p[j - 1] == "*" and dp[0][j - 2]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if p[j - 1] == "*":
                zero = dp[i][j - 2]  # use p[j-2] zero times
                more = p[j - 2] in (s[i - 1], ".") and dp[i - 1][j]  # one more copy eats s[i-1]
                dp[i][j] = zero or more
            else:
                dp[i][j] = p[j - 1] in (s[i - 1], ".") and dp[i - 1][j - 1]
    return dp[n][m]

Mantieni solo due righe

Intuizione

La riga i legge due celle dalla riga i-1, quella diagonale e quella sopra, e una cella della riga stessa, due posizioni a sinistra. Le righe più in alto non vengono più lette. Mantieni due array: prev per la riga completata e cur per la riga che stai riempiendo, e scambiali dopo ogni lettera di s. Le transizioni restano le stesse: zero copie è cur[j-2], una copia in più è prev[j], una corrispondenza semplice è prev[j-1].

Inizia con prev come riga di base per la stringa vuota. Imposta cur[0] su false all’inizio di ogni riga: dopo uno scambio, cur contiene una riga precedente e la prima voce della riga di base è true.

Ogni riga ha m + 1 voci, quindi la memoria passa da circa 10^6 celle a due righe da 1001. A differenza della distanza di modifica, non puoi scambiare i due input per rendere più corte le righe, perché la stringa e il pattern svolgono ruoli diversi.

Algoritmo

Riempi prev con la riga di base: true in 0 e, in j, quando p[j-1] è un asterisco e prev[j-2] è true.
Per ogni lettera di s, imposta cur[0] su false.
Riempi cur[1..m]: una cella con un asterisco è cur[j-2] oppure (l'elemento corrisponde e prev[j]); qualsiasi altra cella è (corrisponde) e prev[j-1].
Scambia prev e cur.
Restituisci prev[m].

def isMatch(s, p):
    n, m = len(s), len(p)
    # prev[j]: do the letters of s before the current one match the first j characters of p?
    prev = [False] * (m + 1)
    prev[0] = True  # row 0: the empty string
    for j in range(2, m + 1):
        prev[j] = p[j - 1] == "*" and prev[j - 2]  # only patterns like x*y*z* match it
    for i in range(1, n + 1):
        cur = [False] * (m + 1)  # cur[0] stays False: an empty pattern matches no letters
        for j in range(1, m + 1):
            if p[j - 1] == "*":
                zero = cur[j - 2]  # use p[j-2] zero times
                more = p[j - 2] in (s[i - 1], ".") and prev[j]  # one more copy eats s[i-1]
                cur[j] = zero or more
            else:
                cur[j] = p[j - 1] in (s[i - 1], ".") and prev[j - 1]
        prev = cur
    return prev[m]

Trappole e casi limite

La maggior parte delle risposte errate dipende dall’asterisco: cosa ripete, quante volte e dove può corrispondere a niente.

Permettere a un asterisco di prendere tutte le lettere che può. a*a con aaa corrisponde, ma un a* avido divora tutte e tre le lettere e l’ultimo a non corrisponde.
Usare dp[i-1][j-2] per un’altra copia. Questo permette all’asterisco di prendere al massimo una lettera, quindi aa con a* risulta false. Rimani nella colonna dell’asterisco: dp[i-1][j].
Lasciare la riga 0 tutta false, tranne la prima cella. Così b con a*b non corrisponde, perché la b ha bisogno che a* corrisponda al prefisso vuoto che la precede.
Confrontare s[i-1] con l’asterisco stesso invece che con il suo elemento p[j-2].
Trattare * come «qualsiasi testo», come nei modelli dei nomi di file. Qui ripete solo l’elemento che lo precede; per qualsiasi testo si usa .*.
Accettare una corrispondenza parziale. t.e corrisponde all’inizio di tree, ma la risposta è false perché rimane una lettera.
Dimenticare cur[0] = false nella versione a due righe. Dopo il primo scambio, cur[0] contiene il true della riga di base.

Domande frequenti4

Qual è la complessità temporale della corrispondenza con le espressioni regolari?

La soluzione con tabella richiede un tempo O(n × m), dove n è la lunghezza di s e m la lunghezza di p, perché ogni cella legge al massimo altre due celle. Richiede O(n × m) di memoria per la tabella completa, oppure O(m) usando due righe. La ricorsione semplice può richiedere un tempo esponenziale con schemi contenenti molti asterischi.

Perché una cella con una stella legge la cella sopra e non quella diagonale?

La cella sopra, dp[i-1][j], segue lo stesso schema con una lettera in meno di s, e l’asterisco è ancora presente. Quindi, dopo aver «mangiato» s[i-1], può mangiare anche s[i-2] e così via risalendo la colonna. La cella diagonale dp[i-1][j-2] rimuove l’asterisco dopo una lettera, consentendo esattamente una copia invece di un numero qualsiasi.

In che modo è diverso dal confronto con caratteri jolly?

Nella corrispondenza con caratteri jolly, come nei pattern dei nomi di file, * funziona da solo e corrisponde a qualsiasi sequenza di caratteri, mentre ? corrisponde a un carattere. Qui * ripete solo l’elemento che lo precede e il pattern per qualsiasi testo è .*. Entrambi si risolvono con una tabella sui prefissi, ma la transizione dell’asterisco è diversa: la corrispondenza con caratteri jolly legge dp[i][j-1] oppure dp[i-1][j].

Perché non usare la libreria di espressioni regolari del linguaggio?

Chi ti fa un colloquio vuole l’algoritmo, non una chiamata a una libreria. C’è anche un rischio concreto: molti motori regex effettuano il matching tramite backtracking, ovvero la ricorsione lenta del primo approccio. Un pattern composto da dieci copie di a* seguite da b, confrontato con una lunga sequenza di lettere a, può far funzionare un motore di questo tipo per minuti. La tabella termina sempre in O(n × m).

Python

def isMatch(s, p):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

s = "moon"
p = "mo*n"

Atteso

true

Regular Expression Matching

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Abbina da sinistra con la ricorsione

Completa una tabella di prefissi

Mantieni solo due righe

Trappole e casi limite

Domande frequenti4

Problemi simili