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) para una cadena de longitud n y un patrón de longitud m , porque cada celda lee como máximo otras dos. Necesita O(n × m) de memoria para la tabla completa, u O(m) con dos filas. La recursión simple puede tardar un tiempo exponencial con patrones que tienen muchos asteriscos.

DifícilProgramación dinámica Recursión

+10

Se te dan 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 repeticiones del elemento que lo precede, que puede ser una letra o un punto. Devuelve true si el patrón coincide con toda la cadena s 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: true si p coincide con todo s, false 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 * y nunca 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 forman exactamente moon.

Entrada: s = "tree"p = "t.e"
Salida: false
Explicación: t.e encaja con tre, el comienzo de tree, pero sobra la última e, 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.

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

Una estrella puede representar cualquier número de repeticiones, y la cantidad adecuada depende de lo que venga después. Trata una letra y su estrella como una sola unidad con dos opciones: omitirla o consumir una letra y permanecer en ella. Una tabla que indica qué prefijos de s coinciden con qué prefijos de p prueba cada opción una vez.

Empareja desde la izquierda con recursión

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

Intuición

Compara los sufijos: match(i, j) indica si s[i:] coincide con p[j:]. Una letra o un punto sin asterisco debe coincidir con s[i], y el resto debe coincidir. Una unidad x* puede tomar cero copias y omitirse, o consumir s[i] y quedarse en la misma unidad, que es como un asterisco toma cualquier cantidad de letras. Las dos ramas abarcan todas las opciones que tiene un asterisco, así que no se omite ninguna coincidencia.

Cada asterisco divide la búsqueda en dos. Para 30 letras a, diez copias de a* y después una b, la recursión prueba alrededor de 8.5 × 10^8 formas de repartir las letras entre los asteriscos antes de responder false, aunque 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 supera el final de p, devuelve si i supera el 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

Sea dp[i][j] un indicador de si las primeras i letras de s coinciden con los primeros j caracteres de p. dp[0][0] es verdadero. En la fila 0, la cadena vacía coincide con un prefijo del patrón solo si todos sus elementos tienen un asterisco, como z* o a*b*.

Una letra o un punto en p[j-1] debe coincidir con s[i-1], y el resto debe coincidir: la celda diagonal, dp[i-1][j-1]. Un asterisco con el elemento x = p[j-2] ofrece dos opciones. Cero copias elimina x*: dp[i][j-2]. Una copia más, cuando x coincide con s[i-1], deja el mismo x* para completar la cadena más corta: dp[i-1][j], la celda de arriba. Cada copia es un paso hacia arriba en la columna del asterisco. Para sky y z*s.*y, la columna de z*s.* es verdadera para s con cero copias, y luego para sk y sky con un paso hacia arriba cada vez.

Cada celda lee la fila de arriba o las celdas de su izquierda, así que al rellenarlas fila por fila, estas ya están listas.

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 solo lee dos celdas de la fila i-1, la diagonal y la celda de arriba, además de su propia celda situada dos posiciones a la izquierda. Mantén dos arreglos, prev y cur, e intercámbialos después de cada letra de s: cero copias es cur[j-2], una copia más es prev[j] y una coincidencia simple es prev[j-1]. La memoria pasa de unos 10^6 celdas a dos filas de 1001. No puedes intercambiar las entradas para acortar las filas, porque la cadena y el patrón cumplen funciones diferentes.

Algoritmo

Rellena prev con la fila 0 de la tabla.
Para cada letra de s, establece cur[0] en false y rellena cur[1..m] con las reglas de la tabla, leyendo prev para la fila de arriba.
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

Permitir que un asterisco tome tantas letras como pueda. a*a coincide con aaa, pero un a* codicioso consume las tres letras y la última a no coincide.
Leer dp[i-1][j-2] para una copia más. Eso permite que un asterisco tome como máximo una letra, así que aa frente a a* da como resultado false.
Dejar la fila 0 en false después de su primera celda. Entonces b frente a a*b no coincide, porque la b necesita que a* coincida con el prefijo vacío.
Comparar s[i-1] con el asterisco en lugar de con su elemento p[j-2]. Entonces a frente a a* no coincide.
No restablecer cur[0] a false en la versión de dos filas. Después de un intercambio, puede contener el true de la fila base, y aab frente a b da como resultado true.

Preguntas frecuentes3

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

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

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

En la coincidencia con comodines, como en los patrones de nombres de archivo, * aparece solo y coincide con cualquier secuencia de caracteres, y ? coincide con un carácter. Aquí, * solo repite el elemento que lo precede, y cualquier texto es .*. Ambos usan una tabla sobre prefijos, pero el asterisco comodín consulta dp[i][j-1] o dp[i-1][j].

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

Un entrevistador quiere el algoritmo, no una llamada a una biblioteca. Muchos motores de expresiones regulares también realizan la coincidencia mediante retroceso, la lenta recursión del primer enfoque, así que diez copias de a* seguidas de b frente a una larga secuencia de letras a pueden hacer que se ejecuten durante minutos. La tabla siempre termina en O(n × m).

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

Prueba #1

Prueba #2

Prueba #3

Argumentos

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

Salida Esperada

true

Regular Expression Matching

Función

Restricciones

Ejemplos

Pistas

Solución

Empareja desde la izquierda con recursión

Completa una tabla de prefijos

Conserva solo dos filas

Errores comunes y casos límite

Preguntas frecuentes3

Problemas similares