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) , em que n é o comprimento de s e m é o comprimento de p , porque cada célula lê no máximo duas outras. Ela precisa de O(n × m) de memória para a tabela completa, ou O(m) com duas linhas. A recursão simples pode levar tempo exponencial em padrões com muitos asteriscos.

Q: Por que uma célula com estrela lê a célula acima, e não a diagonal?

A célula acima, dp[i-1][j] , segue o mesmo padrão, mas com uma letra a menos de s , e o asterisco ainda está nela. Então, depois que o asterisco consome s[i-1] , ele também pode consumir s[i-2] e assim por diante, subindo pela coluna. A célula em estilo diagonal dp[i-1][j-2] remove o asterisco após uma letra, o que permite exatamente uma ocorrência, em vez de qualquer quantidade.

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 a todo o conteúdo de s, e não apenas a uma parte dele, e false caso contrário.

Função

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

sstring: a string a ser correspondida, somente letras minúsculas
pstring: o padrão de letras, pontos e asteriscos
Retornaboolean: verdadeiro se p corresponder a todo s, falso caso contrário

Restrições

1 ≤ s.length ≤ 1000
1 ≤ p.length ≤ 1000
s contém apenas letras minúsculas do inglês.
p contém apenas letras minúsculas do alfabeto inglês, . e *.
Toda * 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* pega as duas 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 apenas a strings de três letras: t, qualquer letra e, em seguida, e. Corresponde a tre no 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, .* aceita o k, e y corresponde a y. Uma letra seguida de asterisco pode representar nada, então um z que nunca aparece em sky não custa nada.

+29 testes ocultos ao enviar

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 quantidade de cópias, e a quantidade certa depende do que vem depois dele. Tentar corresponder ao máximo possível falha: diante de aaa, o padrão a*a faz com que a* consuma as três letras e não deixe nada para o último a. A ideia que resolve isso é tratar uma letra e seu asterisco como uma unidade com dois movimentos: ignorá-la ou deixá-la consumir uma letra e permanecer onde está. Uma tabela registra se cada prefixo de s corresponde a cada prefixo de p, de modo que cada escolha seja testada uma vez, e duas linhas dessa tabela são suficientes.

Correspondência a partir da esquerda com recursão

Correta, mas não termina nos maiores testes

Intuição

Faça com que match(i, j) indique se o sufixo s[i:] corresponde ao sufixo p[j:]. Se o padrão foi totalmente usado, ele corresponde somente se a string também tiver sido totalmente usada. Caso contrário, calcule first: existe uma letra s[i], e p[j] é essa letra ou um ponto.

Agora, olhe um caractere à frente. Se p[j+1] for um asterisco, p[j]* é uma unidade com dois movimentos. Ela pode consumir zero cópias: pule os dois caracteres com match(i, j+2). Ou, se first for verdadeiro, pode consumir uma cópia: consuma s[i] e permaneça na mesma unidade com match(i+1, j), pronta para consumir outra. Permanecer em j é o que permite que um asterisco consuma qualquer número de letras, uma por vez. Sem um asterisco, p[j] precisa corresponder exatamente a uma letra: first and match(i+1, j+1).

Isso é lento porque cada asterisco divide a busca em duas, e uma falha costuma ser encontrada somente no final. Considere 30 letras a contra dez cópias de a* e, em seguida, um b. A recursão tenta todas as maneiras de distribuir algumas ou todas as 30 letras a entre os dez asteriscos, cerca de 8.5 × 10^8 maneiras, e faz cerca de 2 × 10^9 chamadas antes de poder responder false. Os testes grandes têm 1000 letras. No entanto, existem 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 o resultado de verificar se s[i] existe e se 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

Estado. Seja dp[i][j] indicativo de se as primeiras i letras de s correspondem aos primeiros j caracteres de p. O índice 0 representa um prefixo vazio.

Linha e coluna base. dp[0][0] é verdadeiro: um padrão vazio corresponde a uma string vazia. A coluna 0 é falsa abaixo dele, porque um padrão vazio não pode corresponder a uma letra. A linha 0 é a mais sutil: um prefixo do padrão corresponde à string vazia somente se todos os elementos nele tiverem asterisco, como z* ou a*b*. Portanto, dp[0][j] é verdadeiro quando p[j-1] é um asterisco e dp[0][j-2] é verdadeiro.

Transições. Se p[j-1] for uma letra ou um ponto, ele precisa corresponder à última letra s[i-1], e o restante também precisa corresponder: dp[i-1][j-1], na diagonal. Se p[j-1] for um asterisco, seu elemento é x = p[j-2], e o asterisco tem duas possibilidades. Zero ocorrências: remova x* do padrão, dp[i][j-2], duas células à esquerda. Mais uma ocorrência: se x corresponder a s[i-1], essa letra é uma das ocorrências, e o mesmo x* ainda precisa corresponder à string mais curta; portanto, consulte dp[i-1][j], a célula logo acima, na mesma coluna. Cada ocorrência corresponde a um passo para cima nessa coluna, que é como um único asterisco cobre qualquer quantidade de letras.

Aqui está a tabela para sky e z*s.*y, com colunas para os prefixos "", z, z*, z*s, z*s., z*s.*, z*s.*y (T significa verdadeiro, F significa falso). A linha "" é [T, F, T, F, F, F, F]: somente z* pode ser vazio. A linha s é [F, F, F, T, F, T, F]: s corresponde a s com z* vazio acima dele na diagonal, e .* então consome zero ocorrências. A linha sk é [F, F, F, F, T, T, F]: a célula de z*s.* recebe seu valor verdadeiro de mais uma ocorrência; o ponto consome k, consultando o T logo acima dela. A linha sky é [F, F, F, F, F, T, T]: o asterisco do ponto consome y da mesma forma, em um segundo passo para cima na coluna, e então y corresponde a y na diagonal. A última célula é verdadeira.

Cada célula consulta a linha acima ou células à sua esquerda; por isso, preenchê-las linha por linha, da esquerda para a direita, garante que estejam prontas. São (n+1) × (m+1) células, cerca de 10^6 para os maiores testes, com trabalho constante em cada uma.

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]

Mantenha apenas duas linhas

Intuição

A linha i lê duas células da linha i-1, a diagonal e a célula acima, e uma célula da própria linha, duas posições à esquerda. As linhas mais acima nunca são lidas novamente. Mantenha dois arrays: prev para a linha concluída e cur para a linha que você está preenchendo, e troque-os após cada letra de s. As transições continuam iguais: zero cópias é cur[j-2], mais uma cópia é prev[j], uma correspondência simples é prev[j-1].

Comece com prev como a linha base para a string vazia. Defina cur[0] como false no início de cada linha: após uma troca, cur contém uma linha antiga, e a primeira entrada da linha base é true.

Cada linha tem m + 1 entradas, então a memória cai de cerca de 10^6 células para duas linhas de 1001. Diferentemente da distância de edição, você não pode trocar as duas entradas para encurtar as linhas, porque a string e o padrão têm papéis diferentes.

Algoritmo

Preencha prev com a linha base: true em 0 e, em j, quando p[j-1] for um asterisco e prev[j-2] for true.
Para cada letra de s, defina cur[0] como false.
Preencha cur[1..m]: uma célula com asterisco é cur[j-2] ou (o elemento corresponde e prev[j]); qualquer outra célula é (corresponde) e prev[j-1].
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

A maioria das respostas erradas vem do asterisco: o que ele repete, quantas vezes e onde pode corresponder a nada.

Deixar 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 em relação a a* resulta em falso. Permaneça na coluna do asterisco: dp[i-1][j].
Deixar a linha 0 inteira como falsa, exceto a primeira célula. Então b em relação a a*b não corresponde, porque o b precisa que a* corresponda ao prefixo vazio à sua frente.
Comparar s[i-1] com o próprio asterisco em vez de compará-lo com seu elemento p[j-2].
Tratar * como "qualquer texto", como nos padrões de nomes de arquivos. Aqui, ele repete apenas o elemento anterior; qualquer texto é .*.
Aceitar uma correspondência parcial. t.e corresponde ao início de tree, mas a resposta é falsa porque sobra uma letra.
Esquecer cur[0] = false na versão com duas linhas. Após a primeira troca, cur[0] contém o valor verdadeiro da linha base.

Perguntas frequentes4

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

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

Por que uma célula com estrela lê a célula acima, e não a diagonal?

A célula acima, dp[i-1][j], segue o mesmo padrão, mas com uma letra a menos de s, e o asterisco ainda está nela. Então, depois que o asterisco consome s[i-1], ele também pode consumir s[i-2] e assim por diante, subindo pela coluna. A célula em estilo diagonal dp[i-1][j-2] remove o asterisco após uma letra, o que permite exatamente uma ocorrência, em vez de qualquer quantidade.

Qual é a diferença em relação à correspondência com curingas?

Na correspondência com curingas, assim como nos padrões de nomes de arquivos, * funciona por conta própria e corresponde a qualquer sequência de caracteres, e ? corresponde a um caractere. Aqui, * repete apenas o elemento que vem antes dele, e o padrão para qualquer texto é .*. Ambos são resolvidos com uma tabela de prefixos, mas a transição do asterisco é diferente: o curinga lê dp[i][j-1] ou dp[i-1][j].

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

O entrevistador quer o algoritmo, não uma chamada de biblioteca. Também há um risco real: muitos mecanismos de regex fazem correspondências por retrocesso, que é a recursão lenta da primeira abordagem. Um padrão como dez cópias de a* seguidas de b, comparado a uma longa sequência de letras a, pode fazer esse mecanismo levar minutos para executar. A tabela sempre termina em O(n × m).

Python

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

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado

true

Regular Expression Matching

Função

Restrições

Exemplos

Dicas

Solução

Correspondência a partir da esquerda com recursão

Preencha uma tabela de prefixos

Mantenha apenas duas linhas

Armadilhas e casos extremos

Perguntas frequentes4

Problemas parecidos