Regular Expression Matching

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

La soluzione con tabella richiede O(n × m) tempo per una stringa di lunghezza n e un pattern di lunghezza m , perché ogni cella legge al massimo altre due celle. Richiede O(n × m) memoria per la tabella completa, oppure O(m) con due righe. La ricorsione semplice può richiedere un tempo esponenziale con i pattern che contengono molti asterischi.

DifficileProgrammazione dinamica Ricorsione

+10

Hai 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ù copie dell'elemento che lo precede, che può essere una lettera o un punto. Restituisci true se il pattern corrisponde all'intera s 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 a tre, l'inizio di tree, ma l'ultima e rimane fuori e una corrispondenza deve coprire tutto s.

Input: s = "sky"p = "z*s.*y"
Output: true
Spiegazione: z* accetta zero copie di z, s corrisponde a s, .* accetta la k, e y corrisponde a y.

Per approfondire

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

Suggerimenti

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

0 di 3 aperti

Soluzione

Una stella può corrispondere a un numero qualsiasi di copie e il numero giusto dipende da ciò che la segue. Considera una lettera e la sua stella come un’unica unità con due possibilità: saltarla oppure consumare una lettera e restare su di essa. Una tabella che indica quali prefissi di s corrispondono a quali prefissi di p prova una volta ogni possibilità.

Abbina da sinistra con la ricorsione

Corretto, ma non termina sui test più grandi

Intuizione

Confronta i suffissi: match(i, j) indica se s[i:] corrisponde a p[j:]. Una lettera o un punto senza asterisco deve corrispondere a s[i], e il resto deve corrispondere. Un’unità x* prende zero copie e viene saltata, oppure consuma s[i] e resta sulla stessa unità: è così che un asterisco prende un numero qualsiasi di lettere. I due rami coprono tutte le scelte possibili dell’asterisco, quindi nessuna corrispondenza viene tralasciata.

Ogni asterisco divide la ricerca in due. Con 30 lettere a, dieci copie di a* e poi una b, la ricorsione prova circa 8.5 × 10^8 modi di distribuire le lettere tra gli asterischi prima di rispondere false, eppure ci sono 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 è oltre la fine di p, restituisci se i è oltre 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

Lascia che dp[i][j] indichi se le prime i lettere di s corrispondono ai primi j caratteri di p. dp[0][0] è true. Nella riga 0, la stringa vuota corrisponde a un prefisso del pattern solo se ogni elemento al suo interno è seguito da un asterisco, come z* o a*b*.

Una lettera o un punto in p[j-1] deve corrispondere a s[i-1], e il resto deve corrispondere: la diagonale, dp[i-1][j-1]. Un asterisco con elemento x = p[j-2] offre due possibilità. Zero occorrenze elimina x*: dp[i][j-2]. Un'ulteriore occorrenza, quando x corrisponde a s[i-1], lascia lo stesso x* per completare la stringa più corta: dp[i-1][j], la cella sopra. Ogni occorrenza è un passo in su nella colonna dell'asterisco. Per sky e z*s.*y, la colonna di z*s.* è true per s grazie a zero occorrenze, poi per sk e sky grazie a un passo in su per ciascuna.

Ogni cella legge la riga sopra o le celle alla sua sinistra, quindi riempiendo la tabella riga per riga le trova già pronte.

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 solo due celle della riga i-1, quella sulla diagonale e quella sopra, oltre alla propria cella due posizioni a sinistra. Mantieni due array, prev e cur, e scambiali dopo ogni lettera di s: zero copie corrisponde a cur[j-2], un'altra copia corrisponde a prev[j] e una semplice corrispondenza corrisponde a prev[j-1]. La memoria passa da circa 10^6 celle a due righe di 1001 celle. Non puoi scambiare gli input per accorciare le righe, perché la stringa e il pattern svolgono ruoli diversi.

Algoritmo

Riempi prev con la riga 0 della tabella.
Per ogni lettera di s, imposta cur[0] su false e riempi cur[1..m] seguendo le regole della tabella e leggendo prev per la riga sopra.
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

Lasciare che un asterisco prenda tutte le lettere che può. a*a corrisponde a aaa, ma un a* greedy consuma tutte e tre le lettere e l'ultima a non corrisponde.
Leggere dp[i-1][j-2] per una copia in più. Così l'asterisco può prendere al massimo una lettera, quindi aa confrontato con a* dà false.
Lasciare la riga 0 su false dopo la prima cella. Così b confrontato con a*b non corrisponde, perché la b richiede che a* corrisponda al prefisso vuoto.
Confrontare s[i-1] con l'asterisco invece che con il suo elemento p[j-2]. Così a confrontato con a* non corrisponde.
Non reimpostare cur[0] su false nella versione a due righe. Dopo uno scambio, può contenere il true della riga di base, e aab confrontato con b dà true.

Domande frequenti3

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

La soluzione con tabella richiede O(n × m) tempo per una stringa di lunghezza n e un pattern di lunghezza m, perché ogni cella legge al massimo altre due celle. Richiede O(n × m) memoria per la tabella completa, oppure O(m) con due righe. La ricorsione semplice può richiedere un tempo esponenziale con i pattern che contengono molti asterischi.

In che modo è diverso dalla corrispondenza con caratteri jolly?

Nella corrispondenza con caratteri jolly, come nei modelli di nomi di file, * sta da solo e corrisponde a qualsiasi sequenza di caratteri, mentre ? corrisponde a un carattere. Qui * ripete solo l’elemento che lo precede, e qualsiasi testo è .*. Entrambi usano una tabella sui prefissi, ma l’asterisco jolly legge dp[i][j-1] o dp[i-1][j].

Perché non usare la libreria regex del linguaggio?

Chi conduce il colloquio vuole l’algoritmo, non una chiamata a una libreria. Anche molti motori regex eseguono la corrispondenza tramite backtracking, la lenta ricorsione del primo approccio, quindi dieci copie di a* seguite da b confrontate con una lunga sequenza di lettere a possono farli impiegare minuti. La tabella termina sempre in O(n × m).

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

Test #1

Test #2

Test #3

Argomenti

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

Output 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 frequenti3

Problemi simili