Regular Expression Matching

Q: Quelle est la complexité temporelle de la correspondance par expression régulière ?

La solution utilisant un tableau s’exécute en O(n × m) temps, où n est la longueur de s et m la longueur de p , car chaque cellule lit au plus deux autres cellules. Elle nécessite O(n × m) mémoire pour le tableau complet, ou O(m) avec deux lignes. La récursion simple peut prendre un temps exponentiel pour les motifs comportant de nombreuses étoiles.

Q: Pourquoi une cellule étoile lit-elle la cellule au-dessus et non celle en diagonale ?

La cellule au-dessus, dp[i-1][j] , suit le même schéma avec une lettre de moins dans s , et l’astérisque est toujours présent. Ainsi, après que l’astérisque a consommé s[i-1] , il peut aussi consommer s[i-2] , et ainsi de suite en remontant la colonne. La cellule en diagonale dp[i-1][j-2] supprime l’astérisque après une lettre, ce qui permet exactement une occurrence au lieu d’un nombre quelconque.

DifficileProgrammation dynamique Récursivité

+10

On vous donne une chaîne s et un motif p. Dans le motif, une lettre correspond à cette même lettre, un point . correspond à n’importe quelle lettre, et un astérisque * signifie zéro ou plusieurs répétitions de l’élément qui le précède, c’est-à-dire une lettre ou un point. Renvoyez true si le motif correspond à toute la chaîne s, et pas seulement à une partie, et false dans le cas contraire.

Fonction

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

sstring: la chaîne à faire correspondre, lettres minuscules uniquement
pstring: le motif de lettres, de points et d’étoiles
Renvoieboolean: vrai si p correspond à l’ensemble de s, faux sinon

Contraintes

1 ≤ s.length ≤ 1000
1 ≤ p.length ≤ 1000
s ne contient que des lettres minuscules anglaises.
p contient uniquement des lettres minuscules de l’alphabet anglais, . et *.
Chaque * suit une lettre ou un ., donc p ne commence jamais par * et n’a jamais deux astérisques à la suite.

Exemples

Entrée: s = "moon"p = "mo*n"
Sortie: true
Explication: o* prend les deux lettres o, donc m, o* et n épellent exactement moon.

Entrée: s = "tree"p = "t.e"
Sortie: false
Explication: t.e correspond uniquement aux chaînes de trois lettres : t, n’importe quelle lettre, puis e. Il correspond à tre au début de tree, mais le dernier e reste de côté, et une correspondance doit couvrir tout s.

Entrée: s = "sky"p = "z*s.*y"
Sortie: true
Explication: z* prend zéro occurrence de z, s correspond à s, .* prend le k, et y correspond à y. Une lettre suivie d’un astérisque peut ne rien représenter, donc un z qui n’apparaît jamais dans sky ne coûte rien.

+29 tests cachés à la soumission

Pour aller plus loin

Peux-tu également prendre en charge +, une ou plusieurs copies de l’élément qui le précède, avec le même tableau ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Une étoile peut prendre un nombre quelconque de copies, et le bon nombre dépend de ce qui vient après. En prendre autant que possible échoue : avec aaa, le motif a*a permet à a* d’absorber les trois lettres et ne laisse rien pour le dernier a. L’idée qui permet de résoudre le problème consiste à traiter une lettre et son étoile comme une seule unité avec deux possibilités : la sauter, ou lui faire absorber une lettre et la laisser à sa place. Un tableau indique si chaque préfixe de s correspond à chaque préfixe de p, de sorte que chaque choix est essayé une seule fois, et deux lignes du tableau suffisent.

Faire correspondre depuis la gauche avec la récursion

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Soit match(i, j) qui indique si le suffixe s[i:] correspond au suffixe p[j:]. Si le motif est épuisé, il ne correspond que si la chaîne l’est aussi. Sinon, calculons first : il existe une lettre s[i], et p[j] est cette lettre ou un point.

Regardons maintenant le caractère suivant. Si p[j+1] est une étoile, p[j]* forme une unité avec deux possibilités. Elle peut prendre zéro occurrence : ignorer les deux caractères avec match(i, j+2). Ou, si first est vrai, elle peut prendre une occurrence : consommer s[i] et rester sur la même unité avec match(i+1, j), prête à en prendre une autre. Le fait de rester sur j permet à une étoile de prendre autant de lettres que nécessaire, une à la fois. Sans étoile, p[j] doit correspondre exactement à une lettre : first and match(i+1, j+1).

C’est lent, car chaque étoile divise la recherche en deux, et un échec n’est souvent trouvé qu’à la toute fin. Prenons 30 lettres a face à dix copies de a*, puis un b. La récursion essaie toutes les façons de répartir une partie ou la totalité des 30 lettres a entre les dix étoiles, soit environ 8.5 × 10^8 façons, et effectue environ 2 × 10^9 appels avant de pouvoir répondre false. Les grands tests comportent 1000 lettres. Pourtant, il n’existe que (n+1) × (m+1) paires différentes (i, j).

Algorithme

Écrivez match(i, j) pour les suffixes commençant en i et j.
Si j dépasse la fin de p, renvoyez si i dépasse la fin de s.
Définissez first selon que s[i] existe et que p[j] est s[i] ou un point.
Si p[j+1] est une étoile, renvoyez match(i, j+2) ou first and match(i+1, j).
Sinon, renvoyez first and match(i+1, j+1). La réponse est 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)

Remplir un tableau de préfixes

Intuition

État. Soit dp[i][j] l’indication que les i premières lettres de s correspondent aux j premiers caractères de p. L’indice 0 désigne un préfixe vide.

Ligne et colonne de base. dp[0][0] est vrai : un motif vide correspond à une chaîne vide. La colonne 0 est fausse en dessous, car un motif vide ne peut pas correspondre à une lettre. La ligne 0 est plus subtile : un préfixe de motif correspond à la chaîne vide uniquement si chacun de ses éléments est suivi d’une étoile, comme dans z* ou a*b*. Ainsi, dp[0][j] est vrai lorsque p[j-1] est une étoile et que dp[0][j-2] est vrai.

Transitions. Si p[j-1] est une lettre ou un point, il doit correspondre à la dernière lettre s[i-1], et le reste doit aussi correspondre : dp[i-1][j-1], la case en diagonale. Si p[j-1] est une étoile, son élément est x = p[j-2], et l’étoile offre deux possibilités. Zéro occurrence : supprimer x* du motif, dp[i][j-2], deux cases à gauche. Une occurrence de plus : si x correspond à s[i-1], cette lettre est l’une des occurrences, et le même x* doit encore traiter la chaîne plus courte. Il faut donc lire dp[i-1][j], la case juste au-dessus, dans la même colonne. Chaque occurrence correspond à une étape vers le haut dans cette colonne : c’est ainsi qu’une seule étoile couvre un nombre quelconque de lettres.

Voici le tableau pour sky et z*s.*y, avec les colonnes correspondant aux préfixes "", z, z*, z*s, z*s., z*s.*, z*s.*y (T signifie vrai, F signifie faux). La ligne "" est [T, F, T, F, F, F, F] : seul z* peut être vide. La ligne s est [F, F, F, T, F, T, F] : s correspond à s, avec z* vide au-dessus sur la diagonale, puis .* prend zéro occurrence. La ligne sk est [F, F, F, F, T, T, F] : la case correspondant à z*s.* devient vraie grâce à une occurrence de plus, le point correspondant à k ; on lit le T juste au-dessus. La ligne sky est [F, F, F, F, F, T, T] : l’étoile du point absorbe y de la même façon, avec une deuxième étape vers le haut dans la colonne, puis y correspond à y sur la diagonale. La dernière case est vraie.

Chaque case dépend de la ligne du dessus ou des cases à sa gauche. En les remplissant ligne par ligne, de gauche à droite, on trouve donc ces valeurs déjà calculées. Cela représente (n+1) × (m+1) cases, soit environ 10^6 pour les tests les plus grands, avec un travail constant par case.

Algorithme

Crée un tableau dp de (n+1) × (m+1) valeurs fausses et définis dp[0][0] à true.
Pour j de 2 à m, définis dp[0][j] à true lorsque p[j-1] est une étoile et que dp[0][j-2] est true.
Pour chaque cellule où i ≥ 1 et j ≥ 1, si p[j-1] est une étoile, définis-la à dp[i][j-2] ou (p[j-2] correspond à s[i-1] et dp[i-1][j]).
Sinon, définis-la à (p[j-1] correspond à s[i-1]) et dp[i-1][j-1].
Retourne 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]

Ne conserver que deux lignes

Intuition

La ligne i lit deux cellules de la ligne i-1, celle en diagonale et celle du dessus, ainsi qu’une cellule de sa propre ligne, deux positions à gauche. Les lignes situées plus haut ne sont plus jamais lues. Gardez deux tableaux : prev pour la ligne terminée et cur pour la ligne que vous remplissez, puis échangez-les après chaque lettre de s. Les transitions restent les mêmes : zéro copie correspond à cur[j-2], une copie supplémentaire à prev[j], une correspondance simple à prev[j-1].

Commencez avec prev comme ligne de base pour la chaîne vide. Définissez cur[0] sur false au début de chaque ligne : après un échange, cur contient une ancienne ligne, et la première entrée de la ligne de base est true.

Chaque ligne comporte m + 1 entrées, ce qui réduit la mémoire d’environ 10^6 cellules à deux lignes de 1001. Contrairement à la distance d’édition, vous ne pouvez pas échanger les deux entrées pour raccourcir les lignes, car la chaîne et le motif jouent des rôles différents.

Algorithme

Remplissez prev avec la ligne de base : true à 0, et à j lorsque p[j-1] est une étoile et que prev[j-2] est true.
Pour chaque lettre de s, définissez cur[0] sur false.
Remplissez cur[1..m] : une cellule étoile est cur[j-2] ou (l’élément correspond et prev[j]) ; toute autre cellule est (elle correspond) et prev[j-1].
Échangez prev et cur.
Retournez 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]

Pièges et cas limites

La plupart des mauvaises réponses viennent de l’astérisque : ce qu’il répète, combien de fois et où il peut ne rien correspondre.

Laisser un astérisque prendre autant de lettres qu’il le peut. a*a correspond à aaa, mais un a* glouton engloutit les trois lettres et le dernier a échoue.
Lire dp[i-1][j-2] pour une copie supplémentaire. Cela permet à un astérisque de prendre au maximum une lettre, donc aa comparé à a* donne false. Restez dans la colonne de l’astérisque : dp[i-1][j].
Laisser la ligne 0 entièrement à false, à l’exception de la première cellule. Alors b comparé à a*b échoue, car le b a besoin que a* corresponde au préfixe vide qui le précède.
Comparer s[i-1] à l’astérisque lui-même au lieu de le comparer à son élément p[j-2].
Traiter * comme « n’importe quel texte », comme dans les motifs de noms de fichiers. Ici, il ne répète que l’élément qui le précède ; n’importe quel texte s’écrit .*.
Accepter une correspondance partielle. t.e correspond au début de tree, mais la réponse est false, car il reste une lettre.
Oublier cur[0] = false dans la version à deux lignes. Après le premier échange, cur[0] contient le true de la ligne de base.

Questions fréquentes4

Quelle est la complexité temporelle de la correspondance par expression régulière ?

La solution utilisant un tableau s’exécute en O(n × m) temps, où n est la longueur de s et m la longueur de p, car chaque cellule lit au plus deux autres cellules. Elle nécessite O(n × m) mémoire pour le tableau complet, ou O(m) avec deux lignes. La récursion simple peut prendre un temps exponentiel pour les motifs comportant de nombreuses étoiles.

Pourquoi une cellule étoile lit-elle la cellule au-dessus et non celle en diagonale ?

La cellule au-dessus, dp[i-1][j], suit le même schéma avec une lettre de moins dans s, et l’astérisque est toujours présent. Ainsi, après que l’astérisque a consommé s[i-1], il peut aussi consommer s[i-2], et ainsi de suite en remontant la colonne. La cellule en diagonale dp[i-1][j-2] supprime l’astérisque après une lettre, ce qui permet exactement une occurrence au lieu d’un nombre quelconque.

En quoi cela diffère-t-il de la correspondance avec des caractères génériques ?

Dans la correspondance avec jokers, comme dans les motifs de noms de fichiers, * fonctionne de manière autonome et correspond à n’importe quelle suite de caractères, tandis que ? correspond à un seul caractère. Ici, * répète uniquement l’élément qui le précède, et le motif correspondant à n’importe quel texte est .*. Les deux se résolvent à l’aide d’un tableau des préfixes, mais la transition de l’astérisque diffère : la correspondance avec jokers lit dp[i][j-1] ou dp[i-1][j].

Pourquoi ne pas utiliser la bibliothèque d’expressions régulières du langage ?

Un recruteur veut connaître l’algorithme, pas un appel de bibliothèque. Il y a aussi un risque réel : de nombreux moteurs d’expressions régulières font la correspondance par retour arrière, ce qui correspond à la récursion lente de la première approche. Un motif composé de dix copies de a* suivies de b, confronté à une longue suite de lettres a, peut faire tourner un tel moteur pendant plusieurs minutes. La table termine toujours en O(n × m).

Python

def isMatch(s, p):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

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

Attendu

true

Regular Expression Matching

Fonction

Contraintes

Exemples

Indices

Solution

Faire correspondre depuis la gauche avec la récursion

Remplir un tableau de préfixes

Ne conserver que deux lignes

Pièges et cas limites

Questions fréquentes4

Problèmes similaires