Regular Expression Matching

Q: Qual é a complexidade de tempo da correspondência de expressões regulares?

A solução com tabela é executada em tempo O(n × m) para uma string de comprimento n e um padrão de comprimento m , porque cada célula lê no máximo outras duas. Ela precisa de memória O(n × m) para a tabela completa ou O(m) com duas linhas. A recursão simples pode levar tempo exponencial em padrões com muitas estrelas.

DifícilProgramação dinâmica Recursão

+10

Você recebe uma string s e um padrão p. No padrão, uma letra corresponde à mesma letra, um ponto . corresponde a qualquer letra, e um asterisco * significa zero ou mais cópias do elemento imediatamente anterior, que é uma letra ou um ponto. Retorne true se o padrão corresponder à string inteira s e false caso contrário.

Função

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

sstring: a string a ser correspondida, apenas letras minúsculas
pstring: o padrão de letras, pontos e estrelas
Retornaboolean: true se p corresponder a todos os elementos de s, false caso contrário

Restrições

1 ≤ s.length ≤ 1000
1 ≤ p.length ≤ 1000
s contém apenas letras minúsculas do alfabeto inglês.
p contém apenas letras minúsculas do inglês, . e *.
Cada * vem depois de uma letra ou de um ., então p nunca começa com * e nunca tem dois asteriscos seguidos.

Exemplos

Entrada: s = "moon"p = "mo*n"
Saída: true
Explicação: o* captura ambas as letras o, então m, o* e n formam exatamente moon.

Entrada: s = "tree"p = "t.e"
Saída: false
Explicação: t.e corresponde a tre, o início de tree, mas o último e sobra, e uma correspondência deve abranger todo o s.

Entrada: s = "sky"p = "z*s.*y"
Saída: true
Explicação: z* aceita zero ocorrências de z, s corresponde a s, .* consome o k, e y corresponde a y.

Para ir além

Você também pode oferecer suporte a +, uma ou mais cópias do elemento anterior, com a mesma tabela?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Um asterisco pode corresponder a qualquer número de cópias, e a quantidade certa depende do que vem depois dele. Trate uma letra e seu asterisco como uma unidade com dois movimentos: ignore-a ou consuma uma letra e permaneça nela. Uma tabela que mostra quais prefixos de s correspondem a quais prefixos de p testa cada possibilidade uma vez.

Correspondência da esquerda com recursão

Correta, mas não termina nos maiores testes

Intuição

Compare os sufixos: match(i, j) indica se s[i:] corresponde a p[j:]. Uma letra ou um ponto sem asterisco precisa corresponder a s[i], e o restante também precisa corresponder. Uma unidade x* ou usa zero cópias e é ignorada, ou consome s[i] e permanece na mesma unidade, que é como um asterisco aceita qualquer quantidade de letras. Os dois ramos abrangem todas as escolhas que um asterisco pode fazer, então nenhuma correspondência é perdida.

Cada asterisco divide a busca em duas. Para 30 letras a, dez cópias de a* e, em seguida, um b, a recursão tenta cerca de 8.5 × 10^8 maneiras de distribuir as letras entre os asteriscos antes de responder false, embora existam apenas (n+1) × (m+1) pares diferentes (i, j).

Algoritmo

Escreva match(i, j) para os sufixos que começam em i e j.
Se j estiver além do fim de p, retorne se i está além do fim de s.
Defina first como se s[i] existe e p[j] é s[i] ou um ponto.
Se p[j+1] for um asterisco, retorne match(i, j+2) ou first and match(i+1, j).
Caso contrário, retorne first and match(i+1, j+1). A resposta é 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)

Preencha uma tabela de prefixos

Intuição

Seja dp[i][j] uma indicação de se as primeiras i letras de s correspondem aos primeiros j caracteres de p. dp[0][0] é verdadeiro. Na linha 0, a string vazia corresponde a um prefixo do padrão somente se todos os elementos nele tiverem asterisco, como z* ou a*b*.

Uma letra ou ponto em p[j-1] deve corresponder a s[i-1], e o restante também deve corresponder: a diagonal, dp[i-1][j-1]. Um asterisco com o elemento x = p[j-2] tem dois movimentos. Zero cópias remove x*: dp[i][j-2]. Mais uma cópia, quando x corresponde a s[i-1], deixa o mesmo x* para corresponder à string mais curta: dp[i-1][j], a célula acima. Cada cópia é um passo para cima na coluna do asterisco. Para sky e z*s.*y, a coluna de z*s.* é verdadeira para s por zero cópias, depois para sk e sky, um passo para cima em cada caso.

Cada célula consulta a linha acima ou células à sua esquerda, então, ao preencher linha por linha, elas já estarão prontas.

Algoritmo

Crie uma tabela dp com (n+1) × (m+1) valores falsos e defina dp[0][0] como verdadeiro.
Para j de 2 a m, defina dp[0][j] como verdadeiro quando p[j-1] for um asterisco e dp[0][j-2] for verdadeiro.
Para cada célula com i ≥ 1 e j ≥ 1, se p[j-1] for um asterisco, defina-a como dp[i][j-2] ou (p[j-2] corresponder a s[i-1] e dp[i-1][j]).
Caso contrário, defina-a como (p[j-1] corresponder a s[i-1]) e dp[i-1][j-1].
Retorne 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]

Manter apenas duas linhas

Intuição

A linha i lê apenas duas células da linha i-1, a diagonal e a célula acima, além da própria célula que está duas posições à esquerda. Mantenha dois vetores, prev e cur, e troque-os após cada letra de s: zero cópias é cur[j-2], uma cópia a mais é prev[j] e uma correspondência simples é prev[j-1]. A memória cai de cerca de 10^6 células para duas linhas de 1001. Você não pode trocar as entradas para encurtar as linhas, porque a string e o padrão têm papéis diferentes.

Algoritmo

Preencha prev com a linha 0 da tabela.
Para cada letra de s, defina cur[0] como false e preencha cur[1..m] com as regras da tabela, consultando prev para a linha acima.
Troque prev e cur.
Retorne 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]

Armadilhas e casos extremos

Permitir que um asterisco consuma o máximo de letras possível. a*a corresponde a aaa, mas um a* guloso consome as três letras, e o último a não corresponde.
Ler dp[i-1][j-2] para uma cópia a mais. Isso permite que um asterisco consuma no máximo uma letra, então aa comparado com a* resulta em falso.
Deixar a linha 0 como falsa depois da primeira célula. Então b comparado com a*b não corresponde, porque o b precisa que a* corresponda ao prefixo vazio.
Comparar s[i-1] com o asterisco em vez de com seu elemento p[j-2]. Então a comparado com a* não corresponde.
Não redefinir cur[0] como falso na versão com duas linhas. Depois de uma troca, ela pode conter o valor verdadeiro da linha-base, e aab comparado com b resulta em verdadeiro.

Perguntas frequentes3

Qual é a complexidade de tempo da correspondência de expressões regulares?

A solução com tabela é executada em tempo O(n × m) para uma string de comprimento n e um padrão de comprimento m, porque cada célula lê no máximo outras duas. Ela precisa de memória O(n × m) para a tabela completa ou O(m) com duas linhas. A recursão simples pode levar tempo exponencial em padrões com muitas estrelas.

Em que isso é diferente da correspondência com curingas?

Na correspondência com curingas, como nos padrões de nomes de arquivos, * fica sozinho e corresponde a qualquer sequência de caracteres, e ? corresponde a um caractere. Aqui, * repete apenas o elemento anterior, e qualquer texto é .*. Ambos usam uma tabela sobre prefixos, mas o asterisco curinga consulta dp[i][j-1] ou dp[i-1][j].

Por que não usar a biblioteca de expressões regulares da linguagem?

Um entrevistador quer o algoritmo, não uma chamada de biblioteca. Muitos mecanismos de regex também fazem a correspondência por retrocesso, a recursão lenta da primeira abordagem, então dez cópias de a* seguidas de b diante de uma longa sequência de letras a podem fazer com que levem minutos para executar. A tabela sempre termina em O(n × m).

def isMatch(s, p):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

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

Saída Esperada

true

Regular Expression Matching

Função

Restrições

Exemplos

Dicas

Solução

Correspondência da esquerda com recursão

Preencha uma tabela de prefixos

Manter apenas duas linhas

Armadilhas e casos extremos

Perguntas frequentes3

Problemas parecidos