Regular Expression Matching

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

La solution par tableau s’exécute en O(n × m) pour une chaîne de longueur n et un motif de longueur m , car chaque cellule lit au plus deux autres cellules. Elle nécessite O(n × m) de mémoire pour le tableau complet, ou O(m) avec deux lignes. La récursion simple peut prendre un temps exponentiel pour les motifs contenant de nombreuses étoiles.

DifficileProgrammation dynamique Récursivité

+10

Vous obtenez 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 une étoile * signifie zéro ou plusieurs occurrences de l’élément qui la précède, qui est une lettre ou un point. Retournez true si le motif correspond à l’ensemble de s, et false sinon.

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’astérisques
Renvoieboolean: true si p correspond à tout s, false sinon

Contraintes

1 ≤ s.length ≤ 1000
1 ≤ p.length ≤ 1000
s ne contient que des lettres minuscules anglaises.
p contient uniquement des lettres minuscules anglaises, . 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 forment exactement moon.

Entrée: s = "tree"p = "t.e"
Sortie: false
Explication: t.e correspond à tre, le début de tree, mais le dernier e reste en trop, 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.

Pour aller plus loin

Peux-tu aussi 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 répétitions, et le nombre approprié dépend de ce qui la suit. Traite une lettre et son étoile comme une seule unité avec deux mouvements : l’ignorer, ou consommer une lettre et rester dessus. Un tableau indiquant quels préfixes de s correspondent à quels préfixes de p essaie chaque choix une fois.

Correspondre depuis la gauche avec la récursion

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Comparez les suffixes : match(i, j) indique si s[i:] correspond à p[j:]. Une lettre ou un point non suivi d’une étoile doit correspondre à s[i], et le reste doit correspondre. Une unité x* prend soit zéro occurrence et est ignorée, soit consomme s[i] et reste sur la même unité, ce qui permet à une étoile de prendre n’importe quel nombre de lettres. Les deux branches couvrent tous les choix possibles pour une étoile, donc aucune correspondance n’est manquée.

Chaque étoile divise la recherche en deux. Pour 30 lettres a suivies de dix copies de a* puis d’un b, la récursion essaie environ 8.5 × 10^8 façons de répartir les lettres entre les étoiles avant de répondre false, alors qu’il n’existe que (n+1) × (m+1) paires différentes (i, j).

Algorithme

Écrivez match(i, j) pour les suffixes commençant à 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)

Remplissez un tableau de préfixes

Intuition

Soit dp[i][j] qui indique si les i premières lettres de s correspondent aux j premiers caractères de p. dp[0][0] est vrai. Dans la ligne 0, la chaîne vide correspond à un préfixe du motif uniquement si chacun de ses éléments est suivi d’un astérisque, comme z* ou a*b*.

Une lettre ou un point à p[j-1] doit correspondre à s[i-1], et le reste doit aussi correspondre : la diagonale, dp[i-1][j-1]. Un astérisque avec l’élément x = p[j-2] offre deux possibilités. Zéro occurrence supprime x* : dp[i][j-2]. Une occurrence supplémentaire, lorsque x correspond à s[i-1], laisse le même x* pour traiter la chaîne plus courte : dp[i-1][j], la cellule au-dessus. Chaque occurrence correspond à une étape vers le haut dans la colonne de l’astérisque. Pour sky et z*s.*y, la colonne de z*s.* est vraie pour s grâce à zéro occurrence, puis pour sk et sky grâce à une étape vers le haut pour chacune.

Chaque cellule lit la ligne du dessus ou les cellules à sa gauche ; les remplir ligne par ligne permet donc de les trouver déjà calculées.

Algorithme

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

Conservez seulement deux lignes

Intuition

La ligne i ne lit que deux cellules de la ligne i-1, la diagonale et la cellule du dessus, ainsi que sa propre cellule située deux colonnes à gauche. Garde deux tableaux, prev et cur, et échange-les après chaque lettre de s : zéro copie correspond à cur[j-2], une copie supplémentaire à prev[j], et une simple correspondance à prev[j-1]. La mémoire passe d’environ 10^6 cellules à deux lignes de 1001 cellules. Tu ne peux pas échanger les entrées pour raccourcir les lignes, car la chaîne et le motif jouent des rôles différents.

Algorithme

Remplis prev avec la ligne 0 du tableau.
Pour chaque lettre de s, définis cur[0] sur false et remplis cur[1..m] selon les règles du tableau, en lisant prev pour la ligne du dessus.
Échange prev et cur.
Retourne 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

Laisser une étoile prendre autant de lettres que possible. a*a correspond à aaa, mais un a* gourmand engloutit les trois lettres et le dernier a ne correspond plus.
Lire dp[i-1][j-2] pour une copie supplémentaire. Cela permet à une étoile de prendre au plus une lettre, donc aa comparé à a* donne false.
Laisser la ligne 0 à false après sa première cellule. Alors b comparé à a*b échoue, car le b a besoin que a* corresponde au préfixe vide.
Comparer s[i-1] à l’étoile au lieu de comparer son élément p[j-2]. Alors a comparé à a* échoue.
Ne pas réinitialiser cur[0] à false dans la version à deux lignes. Après un échange, cette cellule peut contenir le true de la ligne de base, et aab comparé à b donne true.

Questions fréquentes3

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

La solution par tableau s’exécute en O(n × m) pour une chaîne de longueur n et un motif de longueur m, car chaque cellule lit au plus deux autres cellules. Elle nécessite O(n × m) de mémoire pour le tableau complet, ou O(m) avec deux lignes. La récursion simple peut prendre un temps exponentiel pour les motifs contenant de nombreuses étoiles.

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

Dans la correspondance avec des jokers, comme dans les motifs de noms de fichiers, * fonctionne seul et correspond à toute séquence de caractères, et ? correspond à un seul caractère. Ici, * ne répète que l’élément qui le précède, et tout texte est représenté par .*. Les deux utilisent un tableau sur les préfixes, mais l’astérisque joker consulte 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 l’algorithme, pas un appel à une bibliothèque. De nombreux moteurs d’expressions régulières effectuent également la correspondance par retour arrière, la récursion lente de la première approche ; ainsi, dix copies de a* suivies de b comparées à une longue suite de lettres a peuvent les faire tourner pendant des minutes. Le tableau termine toujours en O(n × m).

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

Test #1

Test #2

Test #3

Arguments

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

Résultat attendu

true

Regular Expression Matching

Fonction

Contraintes

Exemples

Indices

Solution

Correspondre depuis la gauche avec la récursion

Remplissez un tableau de préfixes

Conservez seulement deux lignes

Pièges et cas limites

Questions fréquentes3

Problèmes similaires