Regular Expression Matching

Q: ¿Cuál es la complejidad temporal de la coincidencia con expresiones regulares?

La solución con tabla se ejecuta en tiempo O(n × m) , donde n es la longitud de s y m la longitud de p , porque cada celda lee como máximo otras dos. Necesita O(n × m) de memoria para la tabla completa, o O(m) con dos filas. La recursión simple puede tardar un tiempo exponencial con patrones que contienen muchos asteriscos.

Q: ¿Por qué una celda de estrella lee la celda de arriba y no la diagonal?

La celda de arriba, dp[i-1][j] , sigue el mismo patrón con una letra menos de s , y el asterisco sigue ahí. Así que, después de que el asterisco consuma s[i-1] , también puede consumir s[i-2] , y así sucesivamente hacia arriba por la columna. La celda de estilo diagonal dp[i-1][j-2] elimina el asterisco después de una letra, lo que permite exactamente una copia en lugar de cualquier cantidad.

DifícilProgramación dinámica Recursión

+10

Recibes una cadena s y un patrón p. En el patrón, una letra coincide con esa misma letra, un punto . coincide con cualquier letra, y un asterisco * significa cero o más copias del elemento que tiene justo antes, que es una letra o un punto. Devuelve true si el patrón coincide con toda la cadena s, no solo con una parte de ella, y false en caso contrario.

Función

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

sstring: la cadena que debe coincidir, solo letras minúsculas
pstring: el patrón de letras, puntos y asteriscos
Devuelveboolean: verdadero si p coincide con todo s, falso en caso contrario

Restricciones

1 ≤ s.length ≤ 1000
1 ≤ p.length ≤ 1000
s contiene solo letras minúsculas del inglés.
p contiene solo letras minúsculas del inglés, . y *.
Cada * va después de una letra o de un ., así que p nunca empieza con * ni tiene dos asteriscos seguidos.

Ejemplos

Entrada: s = "moon"p = "mo*n"
Salida: true
Explicación: o* toma ambas letras o, así que m, o* y n deletrean exactamente moon.

Entrada: s = "tree"p = "t.e"
Salida: false
Explicación: t.e coincide solo con cadenas de tres letras: t, cualquier letra y después e. Coincide con tre al inicio de tree, pero la última e queda sin coincidir, y una coincidencia debe abarcar todo s.

Entrada: s = "sky"p = "z*s.*y"
Salida: true
Explicación: z* toma cero copias de z, s coincide con s, .* toma la k e y coincide con y. Una letra con asterisco puede representar nada, así que una z que nunca aparece en sky no cuesta nada.

+29 pruebas ocultas al enviar

Para ir más allá

¿También puedes admitir +, una o más copias del elemento anterior, con la misma tabla?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Un asterisco puede tomar cualquier cantidad de copias, y la cantidad correcta depende de lo que venga después. Tomar tantas como sea posible falla: con aaa, el patrón a*a permite que a* consuma las tres letras y no deja nada para la última a. La idea que lo resuelve es tratar una letra y su asterisco como una sola unidad con dos opciones: omitirla o dejar que consuma una letra y se quede donde está. Una tabla registra si cada prefijo de s coincide con cada prefijo de p, de modo que cada opción se prueba una vez, y bastan dos filas de la tabla.

Coincidir desde la izquierda con recursión

Correcto, pero no termina con las pruebas más grandes

Intuición

Haz que match(i, j) determine si el sufijo s[i:] coincide con el sufijo p[j:]. Si se ha agotado el patrón, solo coincide si también se ha agotado la cadena. De lo contrario, calcula first: hay una letra s[i], y p[j] es esa letra o un punto.

Ahora mira un carácter más adelante. Si p[j+1] es un asterisco, p[j]* es una unidad con dos movimientos. Puede tomar cero copias: omite ambos caracteres con match(i, j+2). O, si se cumple first, puede tomar una copia: consume s[i] y se queda en la misma unidad con match(i+1, j), listo para tomar otra. Quedarse en j es lo que permite que un asterisco tome cualquier cantidad de letras, de una en una. Sin un asterisco, p[j] debe coincidir exactamente con una letra: first and match(i+1, j+1).

Es lento porque cada asterisco divide la búsqueda en dos, y a menudo solo se descubre un fallo al final. Toma 30 letras a frente a diez copias de a* y después una b. La recursión prueba todas las formas de repartir algunas o todas las 30 letras a entre los diez asteriscos, unas 8.5 × 10^8 formas, y realiza unas 2 × 10^9 llamadas antes de poder responder false. Las pruebas grandes tienen 1000 letras. Sin embargo, solo hay (n+1) × (m+1) pares distintos (i, j).

Algoritmo

Escribe match(i, j) para los sufijos que comienzan en i y j.
Si j está más allá del final de p, devuelve si i está más allá del final de s.
Establece first según si s[i] existe y p[j] es s[i] o un punto.
Si p[j+1] es un asterisco, devuelve match(i, j+2) o first and match(i+1, j).
De lo contrario, devuelve first and match(i+1, j+1). La respuesta es 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 tabla de prefijos

Intuición

Estado. Sea dp[i][j] un indicador de si las primeras i letras de s coinciden con los primeros j caracteres de p. El índice 0 representa un prefijo vacío.

Fila y columna base. dp[0][0] es true: un patrón vacío coincide con una cadena vacía. La columna 0 es false debajo de esa celda, porque un patrón vacío no puede coincidir con una letra. La fila 0 es la parte sutil: un prefijo del patrón coincide con la cadena vacía solo si todos sus elementos tienen una estrella, como z* o a*b*. Así que dp[0][j] es true cuando p[j-1] es una estrella y dp[0][j-2] es true.

Transiciones. Si p[j-1] es una letra o un punto, debe coincidir con la última letra s[i-1], y el resto también debe coincidir: dp[i-1][j-1], la diagonal. Si p[j-1] es una estrella, su elemento es x = p[j-2], y la estrella tiene dos movimientos. Cero copias: elimina x* del patrón, dp[i][j-2], dos celdas a la izquierda. Una copia más: si x coincide con s[i-1], esa letra es una de las copias, y el mismo x* todavía tiene que procesar la cadena más corta, así que consulta dp[i-1][j], la celda justo encima, en la misma columna. Cada copia es un paso hacia arriba en esa columna, que es la forma en que una sola estrella cubre cualquier cantidad de letras.

Aquí está la tabla para sky y z*s.*y, con columnas para los prefijos "", z, z*, z*s, z*s., z*s.*, z*s.*y (T es true, F es false). La fila "" es [T, F, T, F, F, F, F]: solo z* puede estar vacío. La fila s es [F, F, F, T, F, T, F]: s coincide con s, con z* vacío arriba en la diagonal, y .* toma después cero copias. La fila sk es [F, F, F, F, T, T, F]: la celda de z*s.* obtiene su valor true de una copia más: el punto consume k, consultando la T que está justo encima. La fila sky es [F, F, F, F, F, T, T]: la estrella del punto consume y de la misma manera, con un segundo paso hacia arriba en la columna, y después y coincide con y en la diagonal. La última celda es true.

Cada celda consulta la fila de arriba o las celdas a su izquierda, así que, al rellenar fila por fila, de izquierda a derecha, esas celdas ya están listas. Son (n+1) × (m+1) celdas, alrededor de 10^6 para las pruebas más grandes, con una cantidad constante de trabajo en cada una.

Algoritmo

Crea una tabla dp de (n+1) × (m+1) valores false y establece dp[0][0] en true.
Para j desde 2 hasta m, establece dp[0][j] en true cuando p[j-1] sea un asterisco y dp[0][j-2] sea true.
Para cada celda con i ≥ 1 y j ≥ 1, si p[j-1] es un asterisco, asígnale dp[i][j-2] o (p[j-2] coincide con s[i-1] y dp[i-1][j]).
De lo contrario, asígnale (p[j-1] coincide con s[i-1]) y dp[i-1][j-1].
Devuelve 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]

Conserva solo dos filas

Intuición

La fila i lee dos celdas de la fila i-1, la diagonal y la celda de arriba, y una celda de la propia fila, dos posiciones a la izquierda. Las filas más arriba nunca se vuelven a leer. Mantén dos arreglos: prev para la fila terminada y cur para la fila que estás rellenando, e intercámbialos después de cada letra de s. Las transiciones siguen siendo las mismas: cero copias es cur[j-2], una copia más es prev[j], una coincidencia simple es prev[j-1].

Empieza con prev como la fila base para la cadena vacía. Establece cur[0] en false al inicio de cada fila: después de un intercambio, cur contiene una fila antigua, y la primera entrada de la fila base es true.

Cada fila tiene m + 1 entradas, así que la memoria baja de aproximadamente 10^6 celdas a dos filas de 1001. A diferencia de la distancia de edición, no puedes intercambiar las dos entradas para hacer que las filas sean más cortas, porque la cadena y el patrón cumplen funciones diferentes.

Algoritmo

Rellena prev con la fila base: verdadero en 0, y en j cuando p[j-1] es un asterisco y prev[j-2] es verdadero.
Para cada letra de s, establece cur[0] en falso.
Rellena cur[1..m]: una celda con un asterisco es cur[j-2] o (el elemento coincide y prev[j]); cualquier otra celda es (coincide) y prev[j-1].
Intercambia prev y cur.
Devuelve 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]

Errores comunes y casos límite

La mayoría de las respuestas incorrectas se deben al asterisco: qué repite, cuántas veces y dónde puede no coincidir con nada.

Dejar que un asterisco tome tantas letras como pueda. a*a frente a aaa coincide, pero un a* codicioso se come las tres letras y la última a no coincide.
Leer dp[i-1][j-2] para obtener una copia más. Eso permite que un asterisco tome como máximo una letra, así que aa frente a a* da como resultado falso. Quédate en la columna del asterisco: dp[i-1][j].
Dejar la fila 0 en falso, excepto la primera celda. Entonces b frente a a*b no coincide, porque la b necesita que a* coincida con el prefijo vacío que tiene delante.
Comparar s[i-1] con el propio asterisco en lugar de compararlo con su elemento p[j-2].
Tratar * como «cualquier texto», como en los patrones de nombres de archivo. Aquí solo repite el elemento que lo precede; cualquier texto se representa con .*.
Aceptar una coincidencia parcial. t.e encaja al principio de tree, pero la respuesta es falsa porque sobra una letra.
Olvidar cur[0] = false en la versión de dos filas. Después del primer intercambio, cur[0] contiene el valor verdadero de la fila base.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de la coincidencia con expresiones regulares?

La solución con tabla se ejecuta en tiempo O(n × m), donde n es la longitud de s y m la longitud de p, porque cada celda lee como máximo otras dos. Necesita O(n × m) de memoria para la tabla completa, o O(m) con dos filas. La recursión simple puede tardar un tiempo exponencial con patrones que contienen muchos asteriscos.

¿Por qué una celda de estrella lee la celda de arriba y no la diagonal?

La celda de arriba, dp[i-1][j], sigue el mismo patrón con una letra menos de s, y el asterisco sigue ahí. Así que, después de que el asterisco consuma s[i-1], también puede consumir s[i-2], y así sucesivamente hacia arriba por la columna. La celda de estilo diagonal dp[i-1][j-2] elimina el asterisco después de una letra, lo que permite exactamente una copia en lugar de cualquier cantidad.

¿En qué se diferencia esto de la coincidencia con comodines?

En la coincidencia con comodines, como en los patrones de nombres de archivo, * funciona por sí solo y coincide con cualquier secuencia de caracteres, y ? coincide con un carácter. Aquí, * solo repite el elemento que lo precede, y el patrón para cualquier texto es .*. Ambos se resuelven con una tabla sobre prefijos, pero la transición de asterisco es diferente: el comodín lee dp[i][j-1] o dp[i-1][j].

¿Por qué no usar la biblioteca de expresiones regulares del lenguaje?

Quien entrevista quiere el algoritmo, no una llamada a una biblioteca. También hay un riesgo real: muchos motores de regex buscan mediante retroceso, que es la recursión lenta del primer enfoque. Un patrón como diez copias de a* seguidas de b, frente a una larga secuencia de letras a, puede hacer que ese motor tarde minutos en ejecutarse. La tabla siempre termina en O(n × m).

Python

def isMatch(s, p):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado

true

Regular Expression Matching

Función

Restricciones

Ejemplos

Pistas

Solución

Coincidir desde la izquierda con recursión

Completa una tabla de prefijos

Conserva solo dos filas

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares